一.线段树的概念
线段树是一种二叉搜索树，每个节点最多有两颗子树，通常称为左、右子树。
这个数据结构将一个区间分成若干个区间，每一个节点存储一个区间 \([L,R]\) 的信息，叶子结点的 \(L\) 等于 \(R\)。
也就是说，我们将 \([1,n]\) 平均分为两个区间，然后一直执行这个操作，分到无法再分为止。
线段树的思想和分治很像：将大区间的信息分为若干个小区间的信息进行操作。
二.线段树的搭建
首先我们要有一个结构体封装节点信息：
struct SegMentTree {
int l;//区间左端点。
int r;//区间右端点。
int sum;//区间和。
int siz;//区间长度。
//Do other things.
}S[N];
我们有一个数组 \([1,2,3,4,5]\)，线段树的搭建如下。
可以发现，对于一个节点 \(u\)，它的左子节点和右子节点的编号分别为 \(2u\) 和 \(2u+1\)，这样我们就能从根节点一直递归下去建树。
显然，节点 \(u\) 的区间和为它的左子节点和右子节点的区间和之和。
这样，就可以写出建树代码了：
#define ls (x) (x * 2)//左子节点。
#define rs (x) (x * 2 + 1)//右子节点。
void build (int nd, int l, int r) {
s[nd].l = l, s[nd].r = r, s[nd].siz = r - l + 1;
//记录信息。
if (l == r) {
s[nd].sum = a[l];//a数组为最初给定的数列。
return ;
}
int mid = l + r >> 1;
build (ls(nd), l, mid);
build (rs(nd), mid + 1, r);
//递归左子树和右子树。
s[nd].sum = s[ls(nd)].sum + s[rs(nd)].sum;
//合并信息。
}
三.线段树的查询
其实单点查询没什么必要学，区间查询可以实现单点查询。
那么这里就只讲解区间查询。
对于一个区间 \([L,R]\)，我们要查询它的区间之和。
同样需要递归记录和。
考虑一个节点 \(u\)， 设它的左端点为 \(u_l\)，右端点为 \(u_l\)，询问区间为 \([L,R]\)。
如果 \(L\le u_l\) 并且 \(R \ge u_r\)，那么直接返回当前节点的区间和即可。
也就是说当当前节点是询问范围的子集时，就直接返回当前节点的区间和。
如果不满足上述条件，那么就需要递归两个子树，通过合并两个区间的信息获得该区间的答案。
这样很容易得出代码了：
ll query (int nd, int l, int r) {
if (l <= s[nd].l && r >= s[nd].r) {
return s[nd].sum;
//当前节点是询问范围的子集时，就直接返回当前节点的区间和。
}
int mid = s[nd].l + s[nd].r >> 1;
ll res = 0;
if (l <= mid) {
res += query (ls(nd), l, r);
//左子树与询问区间有交集，那么递归左子树。
}
if (r > mid) {
res += query (rs(nd), l, r);
//右子树与询问区间有交集，那么递归右子树。
}
return res;
}
当然，如果需要单点查询节点 \(u\)，那么直接将询问区间左右端点都设为 \(u\) 即可。