线段树例题5

发布于 2019-05-14  8 次阅读


题目描述

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


思路

用线段树找到每一个点的位置,将路径上的全部加上这个值,找的时候随便搞一下就可以了


#include 
#include 
#include 
#include 
using namespace std;
#define maxn 1000001
#define max(x,y) x>y?x:y
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
inline int find(int p,int l,int r,int x,int y)
{
    int m=(l+r)>>1;
    if (l==x&&r==y)
        return tot[p];
    if (m>=y) return find(p<<1,l,m,x,y);
    else if (m>1;
    if (l==r)
    {
        tot[p]+=k;
        return 0;
    }
    if (x<=m) insert(p<<1,l,m,x,k);
    else insert(p<<1|1,m+1,r,x,k);
    tot[p]=tot[p<<1]+tot[p<<1|1];
}
int main()
{
    int n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        char ch[2];
        int x,y;
        cin>>ch;
        x=read(); y=read();
        if (ch[0]=='C')
        {
            printf("%d\n",find(1,1,n,x,y));
        }
        else insert(1,1,n,x,y);
    }
}
]]>