动态求连续区间和

题目

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b]的连续和。
输入格式
第一行包含两个整数 n和 m，分别表示数的个数和操作次数。第二行包含 n个整数，表示完整数列。
接下来 m行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1开始计数。
输出格式
输出若干行数字，表示 k=0时，对应的子数列 [a,b]的连续和。
数据范围
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例：
11
30
35

分析

图片来源于百度

线段树也可以解决单点修改，区间查询，结构体中可以是表示求和的sum，也可以是其他的，例如求最大值最小值，

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int w[100006];
struct node{
    int l,r;
    int sum;
}aa[400006];

void pushup(int u)
{  //用子节点的信息去更新父节点
    aa[u].sum=aa[u*2].sum+aa[u*2+1].sum;
}

void build(int u,int l,int r) //根节点是u,在l-r之间建立线段树
{  //建立一个线段树
    if(l==r) aa[u]={l,r,w[l]};
    else
    {
        aa[u]={l,r};//首先对线段树进行初始化
        int mid=(l+r)/2;
        build(u*2,l,mid);build(u*2+1,mid+1,r);//左右递归建立线段树
        pushup(u);//建立之后用子节点的信息更新父节点
    }
}

int query(int u,int l,int r)  //根节点是u，目标区间为l到r
{  //询问操作
    if(l<=aa[u].l&&aa[u].r<=r) return aa[u].sum;//如果当前区间已包括目标区间，直接返回
    int mid=(aa[u].l+aa[u].r)/2;
    int sum=0;
    if(l<=mid) sum+=query(u*2,l,r);
    if(r>mid) sum+=query(u*2+1,l,r);//递归查询
    return sum;
}

void modify(int u,int x,int v) 
{  //更改操作，根节点是u，在位置x上加上v
    if(aa[u].l==aa[u].r) aa[u].sum+=v;
    else
    {
        int mid=(aa[u].l+aa[u].r)/2;
        if(x<=mid) modify(u*2,x,v);
        else modify(u*2+1,x,v);
        pushup(u);
    }
}

int main()
{
    cin>>n>>m;
    int x,a,b;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    while(m--)
    {
        cin>>x>>a>>b;
        if(!x) cout<<query(1,a,b)<<endl;
        else modify(1,a,b);
    }
    return 0;
}