目录
线段树的原理：
树状数组功能：
将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分解为少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对[L,R]的修改或者统计。 作用：对编号连续的一些点的区间信息进行修改或者统计操作 主要操作：区间查询、点更新、区间更新 时间复杂度：修改和统计的复杂度都是O(log(N))
由原理可以看出线段树维护的信息必须满足区间加法
没有懒惰标记的线段树模板：
#include<bits/stdc++.h> using namespace std; const int maxn = 500005 * 4; //线段树范围要开4倍 struct Tree{ int l, r, sum, maxx; }; Tree node[maxn]; //node[maxn]为线段树处理数组 int a[maxn]; //a[maxn]为原数组 void PushUp(int i){ node[i].sum = node[i << 1].sum + node[(i << 1) | 1].sum; node[i].maxx = max(node[i << 1].maxx, node[(i << 1) | 1].maxx); } void build(int i, int l, int r){ node[i].l = l; node[i].r = r; if (l == r){ node[i].maxx = a[l]; node[i].sum = a[l]; return; } int mid = (l + r) / 2; build(i << 1, l, mid); build((i << 1) | 1, mid + 1, r); PushUp(i); } int getsum(int i, int l, int r){ if (node[i].l == l&&node[i].r == r) return node[i].sum; int mid = (node[i].l + node[i].r) / 2; if (r <= mid) return getsum(i << 1, l, r); else if (l > mid) return getsum((i << 1) | 1, l, r); else return getsum(i << 1, l, mid) + getsum((i << 1) | 1, mid + 1, r); } int getmax(int i, int l, int r){ if (node[i].l == l&&node[i].r == r) return node[i].maxx; int mid = (node[i].l + node[i].r) / 2; if (r <= mid) return getmax(i << 1, l, r); else if (l>mid) return getmax((i << 1) | 1, l, r); else return max(getmax(i << 1, l, mid), getmax((i << 1) | 1, mid + 1, r)); } void add(int i, int k, int v) //当前更新的节点的编号为i（一般是1为初始编号，具体得看建立树时使用的第一个编号是什么）。{ //k为需要更新的点的位置，v为修改的值的大小 if (node[i].l == k&&node[i].r == k) //左右端点均和k相等，说明找到了k所在的叶子节点 { node[i].sum += v; node[i].maxx += v; return; //找到了叶子节点就不需要在向下寻找了 } int mid = (node[i].l + node[i].r) / 2; if (k <= mid) add(i << 1, k, v); else add((i << 1) | 1, k, v); PushUp(i); }带有懒惰标记的线段树模板：
#include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 2e5 + 10; #define lrt rt << 1 #define rrt rt << 1 | 1 #define lson l, mid, lrt #define rson mid + 1, r, rrt #define _rep(i,a,n) for (int i = (a); i <= (n); ++i) struct node { int l, r; int sum, max, lazy; int mid () { return (l + r) >> 1; } void set (int l, int r, int lazy = 0) { this->l = l, this->r = r, this->lazy = lazy; } node () { l = r = sum = max = lazy = 0; } node (int l, int r, int s, int m, int la) : l(l), r(r), sum(s), max(m), lazy(la) {} } ; int n, m, k, c; int a[maxn]; char str[7]; node T[maxn << 2]; inline void pushup (int rt) { T[rt].sum = T[lrt].sum + T[rrt].sum; T[rt].max = max(T[lrt].max, T[rrt].max); } inline void pushdown (int rt) { if (T[rt].lazy == 0) return ; T[lrt].lazy += T[rt].lazy; T[lrt].sum += T[rt].lazy * (T[lrt].r - T[lrt].l + 1); T[lrt].max += T[rt].lazy; T[rrt].lazy += T[rt].lazy; T[rrt].sum += T[rt].lazy * (T[rrt].r - T[rrt].l + 1); T[rrt].max += T[rt].lazy; T[rt].lazy = 0; } void build (int l, int r, int rt) { T[rt].l = l, T[rt].r = r, T[rt].lazy = 0; if (l == r) return(void)( T[rt].sum = T[rt].max = a[l] ); int mid = T[rt].mid(); build(lson); build(rson); pushup(rt); } void change (int c, int k, int rt) { if (T[rt].l == T[rt].r && T[rt].l == k) return (void) ( T[rt].sum = c, T[rt].max = c ); int mid = T[rt].mid(); if (k <= mid) change(c, k, lrt); else change(c, k, rrt); pushup(rt); } void update (int c, int l, int r, int rt) { if (T[rt].l >= l && T[rt].r <= r) return (void) ( T[rt].lazy += c, T[rt].sum += c * (T[rt].r - T[rt].l + 1), T[rt].max += c ); pushdown(rt); int mid = T[rt].mid(); if (l <= mid) update(c, l, r, lrt); if (r > mid) update(c, l, r, rrt); pushup(rt); } int querySum (int l, int r, int rt) { if (T[rt].l >= l && T[rt].r <= r) return T[rt].sum; pushdown(rt); int mid = T[rt].mid(); int sum = 0; if (l <= mid) sum += querySum(l, r, lrt); if (r > mid) sum += querySum(l, r, rrt); return sum; } int queryMax (int l, int r, int rt) { if (T[rt].l >= l && T[rt].r <= r) return T[rt].max; pushdown(rt); int mid = T[rt].mid(); int maxx = -inf; if (l <= mid) maxx = max(maxx, queryMax(l, r, lrt)); if (r > mid) maxx = max(maxx, queryMax(l, r, rrt)); return maxx; }
计算 a1+a2+ …… +an = ?
给定 i 和 x ，使得 ai += x
#include<bits/stdc++.h> using namespace std; const int maxn = 50005; const int inf = 0x3f3f3f3f; int bit[maxn], n, a[maxn]; //计算节点的父节点 int lowbit(int x){ return x&(-x);//找到x的二进制的最后一个1 } //修改节点 void add(int i, int x){ while(i <= n){ bit[i] += x; i += lowbit(i); } } void sub(int i, int x){ while(i <= n){ bit[i] -= x; i += lowbit(i); } } //求和 int sum(int i){ int s = 0; while(i > 0){ s += bit[i]; i -= lowbit(i); } return s; } int main(){ int t; scanf("%d", &t); for(int tt=1; tt<=t; ++tt){ printf("Case %d:\n", tt); scanf("%d", &n); memset(bit, 0, sizeof bit); for(int i=1; i<=n; ++i){ scanf("%d", a+i); add(i, a[i]); } char str[10]; while(scanf("%s", str) && str[0]!='E'){ if(str[0] == 'Q'){ int u, v; scanf("%d%d", &u, &v); printf("%d\n", sum(v) - sum(u-1)); } else if(str[0] == 'A'){ int u, v; scanf("%d%d", &u, &v); add(u, v); } else if(str[0] == 'S'){ int u, v; scanf("%d%d", &u, &v); sub(u, v); } } } return 0; }线段树和树状数组两者的复杂度同级，但是树状数组的常数明显优于线段树，编程复杂度也远远小于线段树。
线段树的适用范围大于树状数组，凡是可以使用树状数组解决的问题，使用线段树一定可以解决。树状数组的优点是编程非常简洁，使用lowbit() 可以在很短的几步操作中完成核心操作，代码效率远远高于线段树。
2020-03-01 10:59 PigySu
