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

简介线段树是啥？能干啥？维护线段的一个树形结构
可以用来解决一些区间问题
such as 区间修改区间查询区间最值啥的
同时也可以支持单点修改，只不过显得有点蠢= 。=
为啥要用线段树？因为朴素的做区间操作复杂度会爆炸，而线段树的复杂度是O(logn)O(logn)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]...[1,1],[2,2]...[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); elseadd(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);elsecout << calc(1, 1, n, x, y); }}