看题目名称就知道

这题是树状数组的练习题..

1A掉了

题目链接:http://121.43.100.23/problems/1124/show

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1<<17];
long long c[1<<19];
inline int lowbit(int x)
{
    return x&(-x);
}
long long get_sum(int x)
{
    int i;
    long long sum=0;
    for (i=0;i<20;i++)
    {
        if ((1<<i)&x)
        {
            sum+=c[(x>>i)<<i];
        }
    }
    return sum;
}
void change_val(int x,int y)
{
    for (;x<=(1<<17);)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        c[i+1]=a[i];
    }
    for (i=1;i<=n;i++)
    {
        c[i+lowbit(i)]+=c[i];
    }
    for (i=0;i<m;i++)
    {
        int oper;
        scanf("%d",&oper);
        int x,y;
        scanf("%d%d",&x,&y);
        if (oper==1)
        {
            cout<<get_sum(y)-get_sum(x-1)<<'\n';
        }
        else
        {
            change_val(x,y-a[x-1]);
            a[x-1]=y;
        }
    }
    return 0;
}