引入

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 —— 来自 OI Wiki

线段树的建立与区间查询

建树

线段树的思想在于将序列若干个区间用结点表示，以区间 $[1,n]$ 为根。而对于区间 $[l,r]$，设 $\text{mid}=\lfloor\frac{l+r}{2}\rfloor$，则 $[l,\text{mid}]$ 和 $[\text{mid}+1,r]$ 就是它的左右结点。

如图。使用数组 $d$ 保存线段树，$d_i$ 是线段树上结点 $i$ 所维护的区间的值（图中是区间和）。

不难发现，这样子建出的是一棵完全二叉树，可以使用 $2i,2i+1$ 访问 $i$ 的左右结点。

线段树有如下性质：一段长为 $n$ 的序列，建立的线段树有 $(2n-1)$ 个（有用的）结点，且高度为 $\lceil\log_2n\rceil$.

一般来说，因为存在无用的叶子节点，故数组需要开大一些。经过计算，可以开 $4n$ 的大小。

接下来看看如何建树：

在实现时，我们考虑递归建树。设当前的根节点为 $p$，如果根节点管辖的区间长度已经是 $1$，则可以直接根据 $a$ 数组上相应位置的值初始化该节点。否则我们将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。 —— 来自 OI Wiki

const int N = 1e5;
int d[N << 2];
void pushup(int p) {
	d[p] = d[p * 2] + d[p * 2 + 1];
	return;
} 
void build(int l, int r, int p) {
	if (l == r) {
		d[p] = a[l];
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(l, mid, p * 2), build(mid + 1, r, p * 2 + 1); // 递归建树
	pushup(p); // 向上合并区间和
}

区间查询

要查询 $[l,r]$，则拆成最多为 $O(\log n)$ 个极大的区间，合并即可求得答案。