NYOJ116

注意数组大小

#include <stdio.h>
#include <math.h>
#include <string.h>
typedef struct STU{int grade;//不管是求区间最大值，还是次数，修改的都是grade，也就是grade的求法不同，比如这里是每一个节点的grade一定是他所掌控区间的grade中的最大值int left,right;}STU;//节点个数STU st[2097152];int num[2000001];//由于使用数组表示，所以每一个节点要打上记号int max(int a,int b){return a>b?a:b;}void BuildTree(int i,int left,int right){st[i].left=left;st[i].right=right;st[i].grade=0;//初始化为0if (left==right)//如果是一个点，直接打上记号{num[left]=i;return;}BuildTree(i<<1,left,(int)floor((left+right)/2.0));BuildTree((i<<1)+1,(int)floor((left+right)/2.0)+1,right);//注意括号和优先级}void UpdataTree(int r,int b){if (r==1){st[r].grade+=b;return;//如果是根节点直接返回}st[r].grade=st[r].grade+b;UpdataTree(r/2,b);}int sum;
void Query(int i,int l,int r)//就是要让线段贴近这棵树，所以如果查询的区间（线段）整个在这棵树左边或右边，则直接查询原来的区间,否则从原区间左边到树的中间，再从树的中间+1到查询的右边
{if ((st[i].left==l)&&(st[i].right==r))//如果要查询的区间正好就是节点所控制的区间{sum=sum+st[i].grade;return;}i=i<<1;if (l<=st[i].right)//如果左边有涉及{if (r<=st[i].right)//如果全在左部区间Query(i,l,r);else//不全在左区间Query(i,l,st[i].right);//继续查询在左区间的那部分}i++;if (r>=st[i].left)//如果右边有涉及{if (l>=st[i].left)Query(i,l,r);//全在右区间elseQuery(i,st[i].left,r);}
}
int main()
{int n,m,i,c,a,b;char s[10];scanf("%d%d",&n,&m);BuildTree(1,1,n);for (i=1;i<=n;i++){scanf("%d",&c);UpdataTree(num[i],c);}while(m--){scanf("%s%d%d",s,&a,&b);if (strcmp(s,"QUERY")==0){sum=0;Query(1,a,b);printf("%d\n",sum);}else{UpdataTree(num[a],b);}}return 0;
}