题目
解决:(树状数组)本题是树状数组的基本应用符合两个特征,1、求区间和 2、修改的是单个元素
#include <iostream> #include <cstdio> using namespace std; const int N=1000005; int c[N]; int n; //该函数功能是求出n二进制中最右边0的个数的2次幂,也等于c[n]包含的元素个数num[n-lowbit(n)+1]+...+num[n] int lowbit(int n) { return n&(-n); } //更新数组中pos的值使它加上inc,更新首先更新c[pos]一直更新该点的父节点到顶端 void pl(int pos,int inc) { while(pos<=n) { c[pos]+=inc; pos+=lowbit(pos); } } //该函数功能是求的前n项元素的和 int getsum(int n) { int sum=0; while(n>0) { sum+=c[n]; n-=lowbit(n); } return sum; } int main() { int m,i; char cmd[7]; scanf("%d%d",&n,&m); int num; for(i=1;i<=n;i++) { scanf("%d",&num); pl(i,num); } int a,b; while(m--) { getchar(); scanf("%s%d%d",cmd,&a,&b); if(cmd[0]=='Q')printf("%d\n",getsum(b)-getsum(a-1)); else pl(a,b); } // system("pause"); return 0; }