codevs 1080_线段树练习_树状数组

发布于 2019-05-15  881 次阅读


题目描述

一行N个方格,开始每个格子里都有一个整数。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子区间[a,b]中所有元素的和;修改的规则是指定某一个格子x,加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000,,提问和修改的总数m<10000条。


思路

题目的范围是10000个询问,暴力肯定是不可以的,所以就想到树状数组,随便搞一下就可以了

#include <stdio.h>
int a[100000],f[100000];
int n;
int add(int x,int y)
{
    while (x<=n)
    {
        f[x]+=y;
        x+=x&(-x);
    }
}
int count(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=f[x];
        x-=(x&(-x));
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]);
    }
    int m;
    scanf("%d",&m);
    for (int i=1;i<=n;i++)
    {
        int z,x,y;
        scanf("%d%d%d",&z,&x,&y);
        if (z==1) add(x,y);
        else printf("%d\n",count(y)-count(x-1));
    }
}