题目描述

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

思路

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

#include <stdio.h>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;
#define maxn 1000001
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
struct tree
{
    int x;
}t[maxn*5];
struct edge
{
    int x,next;
}e[maxn*5];
int st[maxn],ed[maxn],ls[maxn],tot[maxn];
int l=0;
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'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<x) return find(p<<1|1,m+1,r,x,y);
    else return find(p<<1,l,m,x,m)+find(p<<1|1,m+1,r,m+1,y);
}
inline int insert(int p,int l,int r,int x,int k)
{
    int m=(l+r)>>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);
    }
}