士兵杀敌（二）

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

输入

只有一组测试数据 第一行是两个整数N,M，其中N表示士兵的个数(1

输出

对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行

样例输入

5 6 1 2 3 4 5 QUERY 1 3 ADD 1 2 QUERY 1 3 ADD 2 3 QUERY 1 2 QUERY 1 5

样例输出

6 8 8 20

代码

#include<stdio.h> int a[1000000],c[1000000],s[1000000],N; int lowbit(int k) { return k&(k^(k-1)); } int sumc(int i) { int j=lowbit(i),sum=0; for(j=i-j+1;j<=i;j++) sum+=a[j]; return sum; } int sum(int i) { int s=0; while(i>0) { s+=c[i]; i-=lowbit(i); } return s; } void add(int pos,int num) { while(pos<=N) { c[pos]+=num; pos+=lowbit(pos); } } int main() { int M,i,x,y,j; char str[10]; scanf("%d %d",&N,&M); for(i=1,a[0]=0;i<=N;i++) scanf("%d",&a[i]); for(i=1;i<=N;i++) c[i]=sumc(i); for(i=1;i<=M;i++) { scanf("%s %d %d",str,&x,&y); if(str[0]=='Q') { s[x-1]=sum(x-1);//注意i到j之间士兵杀敌数为前j个士兵杀敌总数减去前i-1个士兵杀敌的总数 s[y]=sum(y); printf("%d\n",s[y]-s[x-1]); } else { add(x,y); } } return 0; }

测试截图

AC截图