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

简介 线段树是啥？能干啥？

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

=

为啥要用线段树？

因为朴素的做区间 *** 作复杂度会爆炸，而线段树的复杂度是 O ( l o g n ) 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);
	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);
	else
		if (s > m)
			return calc(k + k + 1, m + 1, r, s, t);
		else
			return 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);
	}
}