【luogu3368】模板 树状数组 2

题面

已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的和

题解1

单点查询+区间修改。
-。-说了树状数组模板那就用树状数组。
树状数组维护差分数列即可（差分前缀和是逆操作，树状数组原先的区间查询就变成了单点查询了）。

来介绍一下差分
设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}
也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+….+b[i];(这个很好证的)。
假如区间[2,4]都加上2的话
a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};
发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.
所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:
b[x]=b[x]+k;b[y+1]=b[y+1]-k;

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 500050;

int n, m, a[maxn];
void add(int x, int k){
    for(int i = x; i <= n; i += i&-i)
        a[i] += k;
}
int query(int x){
    int ans = 0;
    for(int i = x; i >= 1; i -= i&-i)ans += a[i];
    return ans;
}

int main(){
    scanf("%d%d", &n, &m);
    int now, last=0;
    for(int i = 1; i <= n; i++){
        scanf("%d", &now);  add(i,now-last);//差分
        last = now;
    }
    for(int i = 1; i <= m; i++){
        int op;  scanf("%d", &op);
        if(op == 1){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x,z);
            add(y+1,-z);
        }else{
            int x;  scanf("%d", &x);
            printf("%d
", query(x));
        }
    }
    return 0;
}

题解2

区间题照例线段树，容易卡常，用手写输入输出。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 500050;
int readint(){
    int op=1,x=0;  char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')op=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return op*x;
}
void outint(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)outint(x/10);
    putchar(x%10+'0');
}

int a[maxn];
struct node{
    int l, r;
    int val, addmark;
}sgt[maxn<<2];
void build(int p, int l, int r){
    sgt[p].l = l, sgt[p].r = r;
    if(l == r){
        sgt[p].val = a[l];
    }else{
        int m = (l+r)/2;
        build(p*2,l,m);
        build(p*2+1,m+1,r);
        sgt[p].val = sgt[p*2].val+sgt[p*2+1].val;
    }
}
void pushdown(int p){
    if(sgt[p].addmark != 0){
        int t = sgt[p].addmark;
        sgt[p].addmark = 0;
        sgt[p*2].addmark += t;
        sgt[p*2+1].addmark += t;
        sgt[p*2].val += (sgt[p*2].r-sgt[p*2].l+1)*t;
        sgt[p*2+1].val += (sgt[p*2+1].r-sgt[p*2+1].l+1)*t;
    }
}
void add(int p, int l, int r, int v){
    if(l <= sgt[p].l && sgt[p].r <= r){
        sgt[p].val += (sgt[p].r-sgt[p].l+1)*v;
        sgt[p].addmark += v;
        return ;
    }
    pushdown(p);
    int m = (sgt[p].l+sgt[p].r)/2;
    if(l <= m)add(p*2,l,r,v);
    if(r > m)add(p*2+1,l,r,v);
    sgt[p].val = sgt[p*2].val+sgt[p*2+1].val;
}
int query(int p, int l, int r){
    if(l <= sgt[p].l && sgt[p].r <= r)return sgt[p].val;
    pushdown(p); //pushdown
    int m = (sgt[p].l+sgt[p].r)/2, ans = 0;
    if(l <= m)ans += query(p*2,l,r);
    if(r > m)ans += query(p*2+1,l,r);
    return ans;
}

int main(){
    int n, m;
    n = readint(), m = readint();
    for(int i = 1; i <= n; i++)a[i] = readint();
    build(1,1,n);
    for(int i = 1; i <= m; i++){
        int op;  op = readint();
        if(op == 2){
            int x;  x = readint();
            outint(query(1,x,x));
            putchar('
');
        }else{
            int x, y, z; x=readint(); y=readint(); z=readint();
            add(1,x,y,z);
        }
    }
    return 0;
}