线段树
线段树可以在 O( logN ) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
注意点：
- 线段树的数组一般要开到4 * N； 位运算的写法为 N >> 2
- 对于懒标记：修改的时候不用用到下面的区间，查询的时候才会用到下面的区间
- 故每次插入懒标记不用递归到叶子节点
建树
void build(int u, int l, int r) { if (l == r) { // 递归边界 f[u] = a[l]; return; } int mid = l + r >> 1; build(u << 1, l, mid); // 建左儿子 build(u << 1 | 1, mid + 1, r); f[u] = f[u << 1] + f[u << 1 | 1]; // 父节点区间和 = 左儿子区间和 + 右儿子区间和 }
单点修改
// 当前修改 u 节点， u 节点所对应区间为[l, r] 要给 a[p] 加上 c void add(int u, int l, int r, int p, int c) { f[u] += c; if (l == r) return; int mid = l + r >> 1; if (p <= mid) // p 在左儿子区间 add(u << 1, l, mid, p, c); else add(u << 1 | 1, mid + 1, r, p, c); }
区间查询
// 当前为 u 节点， u 节点所对应区间为[l, r] 要查询[s, t]区间和 ll query(int u, int l, int r, int s, int t) { if (l == s && r == t) return f[u]; int mid = l + r >> 1; if (t <= mid) // 查询区间完全在左侧 return query(u << 1, l, mid, s, t); else if (s > mid) // 查询区间完全在右侧 return query(u << 1 | 1, mid + 1, r, s, t); else // 左侧部分 + 右侧部分 *注意修改查询区间的边界 return query(u << 1, l, mid, s, mid) + query(u << 1 | 1, mid + 1, r, mid + 1, t); }