什么是线段树？

线段树，是一种二叉搜索树。它可以把一个从1…N的数组可以用二叉树划分为许多区间，这个区间成为二叉树的节点，使用线段树可以大大加快进行区间操作时的速度，同时，区间的最大值、最小值等问题也可以方便地使用线段树求出。

这里借用一下百度百科中的线段树图片来简要说明一下。

其中，[1,10]是我们的操作区间范围，这个节点作为根节点。

其下有两个子节点，一个是[1,5]一个是[6,10]。

对于每个节点[x,y]，当x !=y 时其子节点分别为[x,(x+y)\2]与[(x+y)\2+1,y]

其中，\代表整除

当x == y时，没有子节点，即叶节点。

线段树能做什么？

看到这里，相信很多读者会问，在各个区间的节点上需要保存什么呢？

其实我相信聪明的读者已经看出来了，学过RMQ问题的读者应该已经想到了线段树是一个实现RMQ相比于ST算法占用内存空间更小的算法。实际上正是，例如POJ 2823，用st算法是过不了的。因此，我们还可以在线段树节点上存储区间的最大值、最小值、区间和、区间非0节点数量、区间0节点数量，等等等等。这样，对于一个区间的查询，只需要O(log n)的时间复杂度，相比于O(y-x)，快了许多，因而，线段树非常适合解决区间操作的各类问题。

如何建树？

既然线段树本质上是一棵二叉树，因此我们可以按照正常二叉树的建法来建立线段树。通常有两种，一种是指针，一种是4倍叶节点数的数组（3倍和2倍可以被特殊数据卡掉，具体可以自己证明），这里以指针为例，通俗易懂，但数组方式更省内存空间。（毕竟一个指针的大小为内存地址大小，64位中一个指针抵得上两个int的大小了）

这里以一个用于求和的线段树为例

[sourcecode language=”c”]
#include <cstdio>
int input_array[10000];//注意，
struct SegTreeNode {
int l;
int r;
//l和r为区间的范围，其实可以省略，因为查询的时候自然也会计算出来，这里是为了方便调试，通常我们为了省内存空间会去掉
int sum;
SegTreeNode *L;
SegTreeNode *R;
SegTreeNode():l(0),r(0),sum(0),L(NULL),R(NULL){
//特别要注意赋初始值，cyy曾经因为忘了赋上初始值调了一个WA的题目一个小时
}
}root;
void PushUp(SegTreeNode *N) {//根据子节点的值更新父节点的值
if (N->L != NULL) N->sum += N->L->sum;
if (N->R != NULL) N->sum += N->R->sum;
}
void Build_Tree(SegTreeNode *N,int L,int R) {
N->l = L;
N->r = R;
if (L != R) {//叶节点和非叶节点处理方式不同
int mid = (L + R) / 2;//为了方便大多数读者，这里不使用位运算，实际上会卡常数的数据也很少
N->L = new SegTreeNode;
Build_Tree(N->L,L,mid);
N->R = new SegTreeNode;
Build_Tree(N->R,mid+1,R);
PushUp(N);
}
else {
N->sum = input_array[L];
}
}
void Delete_Tree(SegTreeNode *N) {
if (N->L != NULL) Delete_Tree(N->L);
if (N->R != NULL) Delete_Tree(N->R);
delete N;
}
int main() {
int n;
scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%d",&input_array[i]);
Build_Tree(&root,0,n);
//这里使用GDB调试看看节点情况吧！
return 0;
}
[/sourcecode]

区间操作如何实现？

这里我直接引用洛谷上的线段树1模板

[sourcecode language=”c”]
#include <cstdio>
long long N,M;
struct node {
node *l;
node *r;
long long lv;
long long rv;
long long sum;
long long lan;//懒人标记，其下子节点加上的数
node():l(NULL),r(NULL),lv(0),rv(0),sum(0),lan(0){}
}root;
void build_tree(node *n,long long l,long long r) {
n->lv = l;
n->rv = r;
if (l == r) return;
long long mid = (l + r) >> 1;
n->l = new node;
build_tree(n->l,l,mid);
n->r = new node;
build_tree(n->r,mid+1,r);
}
void update(node *n,long long l,long long r,long long v) {
n->sum += v * (r-l+1);
if (n->lv == n->rv) return;
if (l == n->lv && r == n->rv) n->lan += v;
else {
long long mid = (n->lv + n->rv) >> 1;
if (r < mid + 1) update(n->l,l,r,v);
else if (l > mid) update(n->r,l,r,v);
else {
update(n->l,l,mid,v);
update(n->r,mid+1,r,v);
}
}
}
long long query(node *n,long long l,long long r) {
if (n->lv == l && n->rv == r) return n->sum;
else {
long long mid = (n->lv + n->rv) >> 1;
if (r < mid + 1) return n->lan * (r-l+1) + query(n->l,l,r);
else if (l > mid) return n->lan * (r-l+1) + query(n->r,l,r);
else return n->lan * (r-l+1) + query(n->l,l,mid) + query(n->r,mid+1,r);

}
}
int main() {
int N,M;
scanf("%d%d",&N,&M);
build_tree(&root,1,N);
for (int i=1;i<=N;i++) {
long long x;
scanf("%lld",&x);
update(&root,i,i,x);
}
while (M–) {
int o,x,y;
scanf("%d%d%d",&o,&x,&y);
if (o == 1) {//o == 1时代表操作为加
long long k;
scanf("%lld",&k);
update(&root,x,y,k);
}
else {
printf("%lld\n",query(&root,x,y));
}
}
return 0;
}
[/sourcecode]