P1889 -- 厨房救济

时间限制：1000MS

内存限制：131072KB

Description

众所周知，LZL拥有了N个厨房，曾经因水管问题烦恼一时，在某位神(zhang)秘(ge)男(ge)子(?)给予水管交换器的帮助后，厨房终于正常地运作。不过LZL最近又遇上了新的问题……

由于他做的菜实在是太好吃了（跟他的体型一样），好多人都分批来各个厨房吃饭，其中主要有小Z、小G、小C、小K等人，这让LZL很头疼，因为人实在是太多了，他无法迅速地知道几个厨房或一个厨房有多少人，不能及时地分配厨师应付。

现在，LZL找到了你，请求帮助。

Input Format

第1行N、K 代表有N个厨房，K个批次的人员

第2行有N个数，表示每个厨房现有的人数

从第3至K+2行，每行有一个Q，A和B：

如果Q = 1，则有一个A和B，表示标号为A的厨房加进了B个人（很奇怪，B永远大于0！）

如果Q = 2，则有一个A和B，表示请你输出区间[A,B]厨房的人数总和

Output Format

对于每一个Q=2的询问，输出相应的值

Sample Input

5 31 2 3 4 5 2 1 31 2 22 2 5

Sample Output

616

Hint

30%　N <= 1000 , K <= 1000

50%  N <=10000, K <= 10000

100%  N <= 100000 K <= 100000

所有答案在longlong范围内

 

ZGG: 神秘男子是谁？

LZL：问CK吧，他的题我不知道

ZGG：卧槽，这叫题目？我2秒钟写完了

LZL:……

【题解】

树状数组裸题

1 #include
      
        2 char B[1<<15],*S=B,*T=B; 3 #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++) 4 int n,m,b[100001],c[100001],a[100001]; 5 int lowbit(int x) {
    return x&(-x);} 6 int getint() { 7     int x=0,f=1; char ch=getc(); 8     while(ch<'0'||ch>'9') {
    if(ch=='-') f=-1; ch=getc();} 9     while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0'; ch=getc();}10     return x*f;11 }12 void modify(int x,int delta) {13     14     while(x<=n) {15         c[x]+=delta;16         x+=lowbit(x);17     }18 } 19 int cal(int x) {20     int ret=0;21     while(x!=0) {22         ret+=c[x];23         x-=lowbit(x);24     }25     return ret;26 }27 main() {28     n=getint();m=getint();29     for (int i=1;i<=n;++i) {30         b[i]=getint();31         a[i]=b[i]+a[i-1];32         c[i]=a[i]-a[i-lowbit(i)];33     }34     while(m--) {35         int xx=getint();36         if(xx==2) {37             int p,q;p=getint();q=getint();38             printf("%d\n",cal(q)-cal(p-1));39         }40         if(xx==1) {41             int p,q; p=getint();q=getint();42             modify(p,q);43         }44     }45 }