题目链接：http://acm.ocrosoft.com/contest.php?cid=1690

题目描述

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

输入

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

输出

每行有三个正整数k,a,b(k=0或1, a,b<=n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。对于每个询问输出对应的答案。

样例输入

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

样例输出

10

6

0

6

16

6

24

14

50

41

题目思路：这是一道很裸的线段树单点修改求和题，需要注意的是数据范围已经爆int了，要用long long

代码

#include<bits/stdc++.h>

#define maxn 500005

#define ll long long

using namespace std;

ll ans;

ll tree[maxn*4];

void update(int num,int l,int r,int a,int b)

{

    if(l==r)//如果查到该节点，直接修改

    {

     tree[num]+=b;

     return;

    }

    ll mid=(l+r)/2;//类似二分的思想查

    if(a<=mid)

    update(num*2,l,mid,a,b);//进入下一层

    if(a>mid)

    update(num*2+1,mid+1,r,a,b);

tree[num]=tree[num*2]+tree[num*2+1];//更新该区间的和

}

void query(int num,int l,int r,int a,int b)

{

    if(l==r)

    {

        ans+=tree[num];

        return;

    }

    if(l>=a&&r<=b)

    {

        ans+=tree[num];

        return;

    }

    int mid=(l+r)/2;

//该区间的和为他的左儿子和右儿子区间和的和

    if(a<=mid)

        query(num*2,l,mid,a,b);

    if(b>mid)

        query(num*2+1,mid+1,r,a,b);

    return;

}

int main()

{

    ll n,m,k,a,b;

    scanf("%lld %lld",&n,&m);

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

    {

        scanf("%lld %lld %lld",&k,&a,&b);

        if(k==0)

     update(1,1,n,a,b);//单点修改

        else

        {

            ans=0;

            query(1,1,n,a,b);//查询[a,b]求和

            printf("%lld\n",ans);

        }

    }

    return 0;

}