线段树的原理：将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分解为少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对[L,R]的修改或者统计。
作用：对编号连续的一些点的区间信息进行修改或者统计操作
主要操作：区间查询、点更新、区间更新
时间复杂度：修改和统计的复杂度都是O(log(N))
由原理可以看出线段树维护的信息必须满足区间加法
没有懒惰标记的线段树模板：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 500005 * 4; //线段树范围要开4倍 5 6 struct Tree{ 7 int l, r, sum, maxx; 8 }; 9 10 Tree node[maxn]; //node[maxn]为线段树处理数组 11 int a[maxn]; //a[maxn]为原数组 12 13 void PushUp(int i){ 14 node[i].sum = node[i << 1].sum + node[(i << 1) | 1].sum; 15 node[i].maxx = max(node[i << 1].maxx, node[(i << 1) | 1].maxx); 16 } 17 18 void build(int i, int l, int r){ 19 node[i].l = l; node[i].r = r; 20 if (l == r){ 21 node[i].maxx = a[l]; 22 node[i].sum = a[l]; 23 return; 24 } 25 int mid = (l + r) / 2; 26 build(i << 1, l, mid); 27 build((i << 1) | 1, mid + 1, r); 28 PushUp(i); 29 } 30 31 int getsum(int i, int l, int r){ 32 if (node[i].l == l&&node[i].r == r) 33 return node[i].sum; 34 int mid = (node[i].l + node[i].r) / 2; 35 if (r <= mid) return getsum(i << 1, l, r); 36 else if (l > mid) return getsum((i << 1) | 1, l, r); 37 else return getsum(i << 1, l, mid) + getsum((i << 1) | 1, mid + 1, r); 38 } 39 40 int getmax(int i, int l, int r){ 41 if (node[i].l == l&&node[i].r == r) 42 return node[i].maxx; 43 int mid = (node[i].l + node[i].r) / 2; 44 if (r <= mid) return getmax(i << 1, l, r); 45 else if (l>mid) return getmax((i << 1) | 1, l, r); 46 else return max(getmax(i << 1, l, mid), getmax((i << 1) | 1, mid + 1, r)); 47 } 48 49 void add(int i, int k, int v) //当前更新的节点的编号为i（一般是1为初始编号，具体得看建立树时使用的第一个编号是什么）。{ //k为需要更新的点的位置，v为修改的值的大小 50 if (node[i].l == k&&node[i].r == k) //左右端点均和k相等，说明找到了k所在的叶子节点 51 { 52 node[i].sum += v; 53 node[i].maxx += v; 54 return; //找到了叶子节点就不需要在向下寻找了 55 } 56 int mid = (node[i].l + node[i].r) / 2; 57 if (k <= mid) add(i << 1, k, v); 58 else add((i << 1) | 1, k, v); 59 PushUp(i); 60 }
带有懒惰标记的线段树模板：
1 const int N = 100005; 2 typedef long long LL; 3 LL a[N]; //a[N]储存原数组 4 LL lazy[N << 2]; //空间应该开区间的四倍 5 //！！！懒惰标记（在节点上标记该区间内的所有节点的增量，非必要时不必更新区间内点的sum，以减小时间复杂度 6 int n, q; 7 8 struct Tree{ 9 int l, r; 10 LL sum;//如果有其他的目标值比如max，需要在pushup中更新 11 int mid(){ 12 return (l + r) >> 1; 13 } 14 }tree[N<<2]; 15 16 //更新节点信息 17 void PushUp(int rt){ 18 //节点rt 19 tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; 20 //父节点的sum = 两个子节点sum之和 21 } 22 23 //下推懒惰标记 24 void PushDown(int rt,int m){ 25 //节点rt，区间长度m 26 if(lazy[rt]){ 27 //下推懒惰标记 28 lazy[rt << 1] += lazy[rt]; 29 lazy[rt << 1 | 1] += lazy[rt]; 30 31 //向下更新sum值 32 tree[rt << 1].sum += lazy[rt] * (m - (m >> 1)); 33 tree[rt << 1 | 1].sum += lazy[rt] * (m >> 1); 34 35 //重置“根”节点的懒惰标记 36 lazy[rt] = 0; 37 } 38 } 39 40 //建树 41 void build(int l, int r, int rt){ 42 //区间左端点l，区间右端点r，节点rt 43 tree[rt].l = l; 44 tree[rt].r = r; 45 lazy[rt] = 0; 46 if (l == r) {//当区间缩减到点时 赋予节点的sum 47 tree[rt].sum = a[l]; 48 return; 49 } 50 int m = tree[rt].mid();//tree[].mid()求区间中值函数 51 52 //构建左右子树 53 build(l, m, (rt << 1)); 54 build(m + 1, r, (rt << 1 | 1)); 55 56 //更新节点 57 PushUp(rt); 58 } 59 60 //区间修改：目标区间内每个点的sum都增加c 61 void update(LL c, int l, int r, int rt){ 62 //所有点增量c，目标区间左端点l，目标区间右端点r，节点rt 63 64 //如果刚好存在一个节点的区间与目标区间重合 65 if(tree[rt].l==l && tree[rt].r==r){ 66 67 //！！！懒惰标记（在节点上标记该区间内的所有节点的增量，非必要时不必更新区间内点的sum，以减小时间复杂度 68 lazy[rt] += c; 69 tree[rt].sum += c*(r - l + 1); 70 return; 71 } 72 73 //节点的区间并不能与目标区间重合 74 //如果已经下推到点（无论是否有懒惰标记，都不必更新sum，以减小时间复杂度 75 if(tree[rt].l == tree[rt].r) return; 76 77 int m = tree[rt].mid(); 78 //下推懒惰标记 79 PushDown(rt, tree[rt].r - tree[rt].l + 1); 80 //如果目标区间的右端点 <= 节点区间的中值 81 if (r <= m) update(c, l, r, rt << 1);//专门更新左子树 82 //如果目标区间的左端点 > 节点区间的中值 83 else if(l > m) update(c, l, r, rt << 1 | 1);//专门个更新右子树 84 //如果目标区间涵盖节点区间的中值 85 else { 86 update(c, l, m, rt << 1); 87 update(c, m + 1, r, rt << 1 | 1); 88 } 89 PushUp(rt); 90 } 91 92 //求目标区间和 93 LL Query(int l, int r, int rt){ 94 //目标区间左端点l，目标区间右端点r，节点rt 95 96 //如果节点区间刚好和目标区间重合 97 if (l==tree[rt].l && r==tree[rt].r){ 98 return tree[rt].sum; 99 } 100 101 //节点区间不与目标区间重合 102 int m = tree[rt].mid(); 103 //为了求和需要下推懒惰标记，和更新一些必要节点的sum 104 PushDown(rt, tree[rt].r - tree[rt].l + 1); 105 LL res = 0; 106 //目标区间的右端点 <= 节点区间中值 107 if(r <= m) res += Query(l, r, rt << 1);//向左缩减节点区间 108 //目标区间的左端点 > 节点区间的中值 109 else if(l > m) res += Query(l, r, rt << 1 | 1);//向右缩减节点区间 110 //目标区间涵盖了节点区间的中值 111 else{ 112 res += Query(l, m, rt << 1); 113 res += Query(m + 1, r, rt << 1 | 1); 114 } 115 return res; 116 }
树状数组功能：
计算 a1+a2+ …… +an = ?
给定 i 和 x ，使得 ai += x
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 50005; 5 const int inf = 0x3f3f3f3f; 6 int bit[maxn], n, a[maxn]; 7 8 //计算节点的父节点 9 int lowbit(int x){ 10 return x&(-x);//找到x的二进制的最后一个1 11 } 12 13 //修改节点 14 void add(int i, int x){ 15 while(i <= n){ 16 bit[i] += x; 17 i += lowbit(i); 18 } 19 } 20 void sub(int i, int x){ 21 while(i <= n){ 22 bit[i] -= x; 23 i += lowbit(i); 24 } 25 } 26 27 //求和 28 int sum(int i){ 29 int s = 0; 30 while(i > 0){ 31 s += bit[i]; 32 i -= lowbit(i); 33 } 34 35 return s; 36 } 37 38 int main(){ 39 int t; 40 scanf("%d", &t); 41 for(int tt=1; tt<=t; ++tt){ 42 printf("Case %d: ", tt); 43 scanf("%d", &n); 44 memset(bit, 0, sizeof bit); 45 for(int i=1; i<=n; ++i){ 46 scanf("%d", a+i); 47 add(i, a[i]); 48 } 49 char str[10]; 50 while(scanf("%s", str) && str[0]!='E'){ 51 if(str[0] == 'Q'){ 52 int u, v; 53 scanf("%d%d", &u, &v); 54 printf("%d ", sum(v) - sum(u-1)); 55 } 56 else if(str[0] == 'A'){ 57 int u, v; 58 scanf("%d%d", &u, &v); 59 add(u, v); 60 } 61 else if(str[0] == 'S'){ 62 int u, v; 63 scanf("%d%d", &u, &v); 64 sub(u, v); 65 } 66 } 67 } 68 69 return 0; 70 }
线段树和树状数组两者的复杂度同级，但是树状数组的常数明显优于线段树，编程复杂度也远远小于线段树。
线段树的适用范围大于树状数组，凡是可以使用树状数组解决的问题，使用线段树一定可以解决。树状数组的优点是编程非常简洁，使用lowbit() 可以在很短的几步操作中完成核心操作，代码效率远远高于线段树。