线段树系列之——单点更新与区段总和

线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

接下来的几篇文章我可能会多总结一些关于线段树的题目、扩展及其用法，帮助一些不太懂线段树的ACMer和未来忘记线段树的自己……

例题

题目链接

题意

中文题题意就不解释了。下面我们用糖果来进行相关说明，桌上有n堆糖果，给你每堆糖果的初始数量，然后进行一些操作，这些操作可以往指定的糖果堆里放糖果，也可以往指定的糖果堆里拿走糖果，也可以询问第a~b堆糖果的总数是多少。对于每次询问，输出这几堆糖果的总数

导学

可能读者以前没接触过线段树，我借这道题形容一下。如果你用数组来维护这一堆糖果，那么增加和减少可能比较方便，但是计算总和的时候每一次询问操作都需要重新循环，肯定就超时了

那么使用线段树的好处在哪里呢？比如10堆糖果，它把这线型的10堆糖果变成了树型。整一棵树的所有叶节点存储的是每一堆糖果的数量，而其叶节点的父节点则存储了该节点下所有子节点的糖果数的总和。依次往上，根节点存储的也就是所有糖果堆的总和

增加/减少糖果时，找到该糖果所在的叶节点的位置，更新，并且更新所有与该叶节点有关的“父节点”，在查询时，就不需要重新计算了，将指定父节点的位置相加即可。

解析

在这题中，首先建立一个空的线段树，即假设每堆糖果的数量为0

void build(int l,int r,int p){ //构造线段树
    tree[p].left=l;   //节点所表示的范围起点
    tree[p].right=r;  //节点所表示的范围终点
    tree[p].value=0;  //糖果的数量初始置0
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,p*2);  //依次建立子节点，直到处理到叶节点为止
    build(mid+1,r,p*2+1);
}
……
cin>>n;   //糖果的堆数
build(1,n,1);

然后得到每一堆糖果的具体数量。对于每一堆的数量，其实就相当于在原来置0的情况下，进行依次增加操作，往第i堆中增加value个糖果。

void add(int k,int p,int value){
    if(tree[p].left==k&&tree[p].right==k){   //如果找到了对应位置的叶子节点，就进行增加操作
        tree[p].value+=value;
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;  //从子节点中寻找
    if(k<=mid) add(k,p*2,value);
    else add(k,p*2+1,value);
    tree[p].value = tree[2*p].value+tree[2*p+1].value;  //子节点更新了，父节点也要更新
}
……
for(i=1;i<=n;i++){
    scanf("%d",&num);
    add(i,1,num);
}

然后，在上述操作的基础上，我们发现已经解决了题目要求的增加和减少的命令了，因为减少n等于增加-n。还有最后一个查询的操作，也就是查询a~b堆的总数

void search(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){  //如果这个节点的范围完全吻合所需要查找的范围
        sum+=tree[p].value;  //直接增加
        return;   //加完就跑
    }
    //如果这个节点的范围不满足怎么办？
    int mid = (tree[p].left+tree[p].right)/2;  //取当前范围的中点
    if(r<=mid) search(l,r,2*p);  //如果所求范围在中点左边，往左子树找
    else if(l>mid) search(l,r,2*p+1);  //如果所求范围在中点右边，往右子树找
    else{
        //如果mid在所有范围当中，也就是左子树也有，右子树也有，那就都找，但是需要处理一下范围，不能直接传递l和r
        search(l,mid,2*p);
        search(mid+1,r,2*p+1);
    }
}
……
sum=0;
search(num1,num2,1);
cout<<sum<<endl;

上面的查询操作也是这个代码的核心操作，和数组查询不同的是，数组查询每次都是在查询叶节点，而线段树几乎不会到叶节点，总是到某个父节点就停下了，所以大大减少了操作次数

AC代码

#include <iostream>
#include <string.h>
#include <stdio.h>
#define M 50005
using namespace std;
int sum;
struct node{
    int left;
    int right;
    int value;
}tree[4*M]; //大小为预定长度的4倍
void build(int l,int r,int p){ //构造线段树
    tree[p].left=l;   //节点所表示的范围起点
    tree[p].right=r;  //节点所表示的范围终点
    tree[p].value=0;  //糖果的数量初始置0
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,p*2);  //依次建立子节点，直到处理到叶节点位置
    build(mid+1,r,p*2+1);
}
void add(int k,int p,int value){
    if(tree[p].left==k&&tree[p].right==k){   //如果找到了对应位置的叶子节点，就进行增加操作
        tree[p].value+=value;
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;  //从子节点中寻找
    if(k<=mid) add(k,p*2,value);
    else add(k,p*2+1,value);
    tree[p].value = tree[2*p].value+tree[2*p+1].value;  //子节点更新了，父节点也要更新
}
void search(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){  //如果这个节点的范围完全吻合所需要查找的范围
        sum+=tree[p].value;  //直接增加
        return;   //加完就跑
    }
    //如果这个节点的范围不满足怎么办？
    int mid = (tree[p].left+tree[p].right)/2;  //取当前范围的中点
    if(r<=mid) search(l,r,2*p);  //如果所求范围在中点左边，往左子树找
    else if(l>mid) search(l,r,2*p+1);  //如果所求范围在终点右边，往右子树找
    else{   //如果mid在所有范围当中，也就是左子树也有，右子树也有，那就都找，但是需要处理一下范围，不能直接传递l和r
        search(l,mid,2*p);
        search(mid+1,r,2*p+1);
    }
}
int main(){
    char str[10];
    int T,n,i,k,num,num1,num2;
    cin>>T;
    for(k=1;k<=T;k++){
        cin>>n;   //堆数
        build(1,n,1);
        for(i=1;i<=n;i++){
            scanf("%d",&num);
            add(i,1,num);
        }
        cout<<"Case "<<k<<":"<<endl;
        while(scanf("%s",str)&&strcmp(str,"End")!=0){
            scanf("%d%d",&num1,&num2);
            if(strcmp(str,"Add")==0)
                add(num1,1,num2);
            else if(strcmp(str,"Sub")==0)
                add(num1,1,-num2);
            else{
                sum=0;
                search(num1,num2,1);
                cout<<sum<<endl;
            }
        }
    }
    return 0;
}