士兵杀敌（二）

描述

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

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

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

输入

只有一组测试数据
第一行是两个整数N,M，其中N表示士兵的个数(1 随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.

输出

对于每次查询，输出一个整数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

士兵杀敌(一) 数组是固定的，所以可以用一个sum数组来保存每个元素的和就行，但是不能每次都加，因为那样会超时，查询次数太多。但是这个士兵杀敌(二)就不能用那个方法来解了，因为这个是动态的，中间元素的值可能会变化，所以引出一个新的东西来。刚开始想了一下，实在是没有想到方法，就去讨论区看了看，一看好像都说用树状数组，就去找树状数组的用法。
先上图，看着图解释容易理解点。
数组A是原数组中的元素，数组C是树状数组中的元素，图中C数组的元素组成为A中的某些元素之和，这些元素的个数取决于它的下标能被多少个2整除，像C[1] = A[1]; C[2] = A[1] + A[2]; C[3] = A[3]; C[4] = A[1] + A[2] + A[3] + [4] = C[2] + C[3]; ……这些个数可以写一个通式C[i] = A[n - 2^k + 1] + ……+A[i]; 其中k为 i 的二进制中从右往左数的 0 的个数 ，就像6有一个， 6可以写成 2 × 3， 所以C[6] = A[5] + A[6]; 所以可以定义一个函数来求这个数.
6的二进制为0110
5的二进制为0101<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD48cD42XjUgPSAwMDExPC9wPjxwPjYmYW1wOyg2XjUpID0gMDAxMCA9IMquvfjWxtbQtcQyPC9wPjxwPsv50tS6r8r9v8nS1NXiw7TQtDwvcD48cHJlIGNsYXNzPQ=="brush:java;">int lowbit(int N)//求n中有多少个能被2的多少次幂整除的，即2^k， 也就是树状数组的作用域
{
    return N & (N ^ (N - 1));
}

也可以写成

int lowbit(int N)//求n中有多少个能被2的多少次幂整除的，即2^k， 也就是树状数组的作用域
{
    return N & (-N);
}

更改一个数的值， 就要更改次数在树状数组中的所有祖先，不过这个时间复杂度是O(logn); 下面是更改值(添加杀敌数)的函数

void add(int pos, int num)//添加新值到树状数组中
{
    while(pos <= n)
    {
        tmp[pos] += num;
        pos += lowbit(pos);
    }
}

下面就是求和函数， 因为这种方法之所以快，是求他的最小树根节点的和， 最小树的个数为当前要求的n的二进制中为1的个数，即展开式中能写成不同2的幂指数的项数，

例如: 15 = 2^3 + 2^2 + 2^1 + 2^0; 所以n = 15时， 最小数有四个，求和的时间复杂度为O(logn);

int Sum(int N)//求前N个数的和
{
    int sum = 0;
    while(N > 0)
    {
        sum += tmp[N];
        N -= lowbit(N);
    }
    return sum;
}

关键就是这三步， 这三步搞明白了，基本上就不成问题了，但是，当时按照 杀敌(一) 中的思维，还统计了一个总数，那样不会快，反而会慢，所以直接求就行，下面是完整的代码

#include
       
        
#include
        
          int a[1000010]; int n,m; int lowbit(int N)//求n中有多少个能被2的多少次幂整除的，即2^k， 也就是树状数组的作用域 { return N&(-N); } void asd(int i,int M)//添加新值到树状数组中 { while(i<=n) { a[i]+=M; i+=lowbit(i); } } int sum(int N)//求前N个数的和 { int sum=0; while(N>0) { sum+=a[N]; N-=lowbit(N); } return sum; } int main() { int i,t,a,b; char str[10]; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&t); asd(i,t); } while(m--) { scanf("%s %d %d",str,&a,&b); if(!strcmp(str,"QUERY")) printf("%d\n",sum(b)-sum(a-1)); else asd(a,b); } return 0; } 
        
       

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： hdu 5035 概率论

下一篇： HDU 3954 Level up（线段树)

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");