树状数组

//对于树状数组，有利有弊，代码也是的确简单，常用在动态更新求区间和
//当然，某些情况下的求解最大值也是可以做的，代码也的确比线段树好写的多
//单点更新的操作可以利用Sum找出单点值，再用Add更新两次即可

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;

#define lowbit(x) (x&(-x))
const int MaxN=10001000;
long long arr[MaxN];
int n;

void Build()
{
    memset(arr,sizeof(arr));
    long long temp;
    int j;
    for(int i=1; i<=n; ++i)
    {
        scanf("%lld",&temp);
        j=i;
        while(j<=n)
        {
            arr[j]+=temp;
            j+=lowbit(j);
        }
    }
}
void Add(int x,int val)
{
    while(x<=n)
    {
        arr[x]+=val;
        x+=lowbit(x);
    }
}
long long sum(int x)
{
    long long ans=0;
    while(x>0)
    {
        ans+=arr[x];
        x-=lowbit(x);
    }
    return ans;
}


int main()
{
    int temp,take;
    while(~scanf("%d",&n))
    {
        Build();//建树

        while(scanf("%d",&take))
        {
            if(take==1)//单点添加
            {
                int x,val;
                scanf("%d%d",&x,&val);
                Add(x,val);
            }
            else//求区间和
            {
                int l,r;
                scanf("%d%d",&l,&r);
                printf("%lldn",sum(r)-sum(l-1));
            }
        }

    }
    return 0;
}