线段树之Sum

题面：

给定一数列，规定有两种操作，一是修改某个元素，二是求区间的连续和。

Input:

输入数据第一行包含两个正整数n,m(n<=100000,m<=500000),以下是m行，

每行有三个正整数k,a,b(k=0或1, a,b<=n).

k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。

Output:

对于每个询问输出对应的答案。

Sample Input:

10 20

0 1 10

1 1 4

0 6 6

1 4 10

1 8 9

1 4 9

0 10 2

1 1 8

0 2 10

1 3 9

0 7 8

0 3 10

0 1 1

1 3 8

1 6 9

0 5 5

1 1 8

0 4 2

1 2 8

0 1 1

Sample Output:

10

6

0

6

16

6

24

14

50

41

Solution:

线段树模板题，单点修改，区间询问，tree数组维护和

Code:

#include<bits/stdc++.h>

using namespace std;

int n,m,a[1000001];

struct sgt{

    int tree[500001];

    void build(int k,int l,int r){

        if(l==r){

            tree[k]=a[l];

            return ;

        }

        int mid=(l+r)>>1;

        build(k<<1,l,mid);build(k<<1|1,mid+1,r);

        tree[k]=tree[k<<1]+tree[k<<1|1];

    }//建树

    void change(int x,int v,int l,int r,int k){

        if(l==x&&r==x){

            tree[k]+=v;return;

        }

        int mid=(l+r)>>1;

        if(x<=mid)change(x,v,l,mid,k<<1);

        else change(x,v,mid+1,r,k<<1|1);

        tree[k]=tree[k<<1]+tree[k<<1|1];

    }//单点修改

    int query(int l,int r,int L,int R,int k){

        if(l>R||r<L)return 0;

        if(l>=L&&r<=R)return tree[k];

        int re=0;

        int mid=(l+r)>>1;

        re+=query(l,mid,L,R,k<<1);

        re+=query(mid+1,r,L,R,k<<1|1);

        return re;

    }//区间查询

}T;//结构体存线段树

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

    return x*f;

}

int main(){

    n=read();m=read();

    T.build(1,1,n);

    for(int i=1;i<=m;i++){

        int opt,l,r;

        opt=read();l=read();r=read();

        if(opt==0)T.change(l,r,1,n,1);

        if(opt==1)printf("%d\n",T.query(1,n,l,r,1));

    }

    return 0;

}

巴特西