数据结构初级——没有标记的线段树

简介

线段树是啥？能干啥？

维护线段的一个树形结构
可以用来解决一些区间问题
such as 区间修改 区间查询 区间最值啥的
同时也可以支持单点修改，只不过显得有点蠢=。=

为啥要用线段树？

因为朴素的做区间操作复杂度会爆炸，而线段树的复杂度是$O(logn)$

啥是线段？

就是一个区间了=。=

线段树上的每个点，代表了区间的一段
根节点存储区间[1, n]的信息
每个节点会有两个儿子，将区间从中间断开，分为
[ 1 , ( n + 1 ) 2 ] , [ ( n + 1 ) 2 + 1 , n ] [1, \frac{(n + 1)}{2}], [\frac{(n + 1)}{2} + 1, n] [1,2(n+1)​],[2(n+1)​+1,n]

直到划分到点$[1,1],[2,2]...$
这样就构成了一个二叉树，所以线段树得入门是肥肠简单的
在实现的时候只需要开4倍空间就可以了，因为所有的节点数量不会超过4n
（不会证）
一般在建树的时候会以1为下标开始建树
这样的话左儿子的下标就可以是k + k，右儿子的下标就是k + k + 1
也就是k >> 1和k >> 1 | 1或者k * 2和k * 2 + 1

上例子

简单的模板题

#include using namespace std;int n, m, a[500001], f[2000001];void buildtree(int k, int l, int r) {if (l == r) {f[k] = a[l];return;// 到底回溯}int m = (l + r) >> 1;buildtree(k + k, l, m);buildtree(k + k + 1, m + 1, r);f[k] = f[k + k] + f[k + k + 1];}/*l, r: 下标为k的点对应的区间x, y: 将第x个数加y*/inline void add(int k, int l, int r, int x, int y) {f[k] += y;if (l == r) return;int m = (l + r) >> 1;if (x <= m) add(k + k, l, m, x, y);else add(k + k + 1, m + 1, r, x, y);}/*s, t:求区间[s, t]的和*/int calc(int k, int l, int r, int s, int t) {if (l == s && r == t)return f[k];int m = (l + r) >> 1;if (t <= m) return calc(k + k, l, m, s, t);elseif (s > m)return calc(k + k + 1, m + 1, r, s, t);elsereturn calc(k + k, l, m, s, m) + calc(k + k + 1, m + 1, r, m + 1, t);}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];buildtree(1, 1, n);// 以下标为1的点为根节点for (int i = 1; i <= m; i++) {int t, x, y;cin >> t >> x >> y;if (t == 1) add(1, 1, n, x, y);else cout << calc(1, 1, n, x, y);}}