soj2745树状数组.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 62 行

#include<stdio.h>

#define MAX 100001

int a[MAX];

int c[MAX];

int n;

int lowbit(int x)
{
    return x&(x^(x-1));
}

void change(int k,int delta)
{
    while(k<=n)
    {
        c[k]=c[k]+delta;
        k=k+lowbit(k);
    }
}

int getsum(int k)
{
    int t=0;
    while(k>0)
    {
        t=t+c[k];
        k=k-lowbit(k);
    }
    return t;
}

int main(void)
{
    int m;
    while(scanf("%d%d",&n,&m)==2)
    {
        int i;
        for(i=1;i<=n;i++)
        {
            c[i]=a[i]=0;
        }
        int b,p,q;
        while(m--)
        {
            scanf("%d%d%d",&b,&p,&q);
            if(b==0)
            {
                printf("%d\n",getsum(q+1)-getsum(p));//Refer to 0......n-1 
            }
            if(b==1)
            {
                change(p+1,q);//Refer to 0.......n-1
            }
        }
    }
    return 0;
}