【分治】线段树 SegmentTree

算法描述

线段树是一种能够处理区间修改和区间查询的数据结构。

顾名思义，线段树就是一种存储着线段数据的树形结构。它的每个节点都表示一个线段区间，每个节点的孩子节点存储的就是该区间的左半段和右半段。每个线段区间都存储着一个值，一般是区间和，也有可能是区间最大/最小值。

算法实现

线段树使用数组实现，根节点编号为 \(1\) 表示区间 \(1\) 到 \(n\)，左子节点是 \(i \times 2\)，右子节点是 \(i \times 2 + 1\).

ll lc(ll p){return p << 1;}
ll rc(ll p){return p << 1 | 1;}

初始化

从根节点开始，不断的分割区间直到该区间只剩单个数，然后开始向上汇总。传入两个变量 l 和 r， 表示当前节点表示的线段。

void pushUp(ll p){
	sum[p] = sum[lc(p)] + sum[rc(p)];
}

void build(ll p, ll l, ll r){
	if(l == r){
		sum[p] = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	pushUp(p); 
}

区间查询

区间修改

如果每次修改都从上到下全改一遍，复杂度得 \(\mathcal{O}(n)\) ，太浪费时间了。