本文主要是介绍NY--116 -- 士兵杀敌（二） [树状数组是也]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
士兵杀敌（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：5
- 描述 南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。 小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。 南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。
输入
只有一组测试数据
第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000)
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.
- 输出
对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行
- 样例输入
- 样例输出 6 8 8 20
Code:
这里求和的时候考虑情况太多了点....有时候专家级别的指导思想还是没好处的...
简简单单多好~
#include"stdio.h"
#include"stdlib.h"int n,m;
int sum[1000000];
int ans;
int minpower(int x)//最小幂
{return x&(-x);
}void update(int i,int add) //有一个数改变,就把之后含有该项的和全部改变
{while(i<=n){sum[i] += add;i += minpower(i);}
}int getsum(int a,int b,int ans)//求区间a~b的士兵共杀了多少敌人
{ //这里求和想的太麻烦了,考虑情况太多了...其实就把b之前的一直加到1,再减去a之前加到1的就可以了.. int j = minpower(b);int sub = 0;ans += sum[b];
// printf("ans:%d b:%d\n",ans,b);if((b-j+1)>a) //没有加到a的话,接着加上剩余的 {getsum(a,b-j,ans);} else if((b-j+1)==a) return ans; //如果正好加到a,返回 else{return (ans - getsum(b-j+1,a-1,sub)); //加到a前面的话减去多加的值 }
} int main()
{char order[6];int i,j,k,a,b;scanf("%d%d",&n,&m);sum[0] = 0;for(i=1;i<=n;i++){scanf("%d",&sum[i]);j = minpower(i);for(k=i-1;k>=i-j+1;)//边输入边求和 {sum[i] += sum[k];k = k - minpower(k);} }
// printf("--------\n");
// for(i=1;i<=n;i++)
// printf("%d ",sum[i]);
// printf("\n--------\n");for(j=1;j<=m;j++){ans = 0;getchar();scanf("%s%d%d",order,&a,&b);switch(order[0]){case 'q':case 'Q':// printf("-----\n");printf("%d",getsum(a,b,ans));if(j!=m) printf("\n");break;case 'A':case 'a':update(a,b);// printf("--------\n");// for(i=1;i<=n;i++)// printf("%d ",sum[i]);// printf("\n--------\n"); break; } }return 0;
}
这篇关于NY--116 -- 士兵杀敌（二） [树状数组是也]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
