本质上当然可以用线段树，但还是可以用树状数组维护一个差分。

P3368 【模板】树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上$x$。

2.求出某一个数的值。

输入输出格式

输入格式

第一行包含两个整数$N,M$，分别表示该数列数字的个数和操作的总个数。

第二行包含$N$个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来$M$行每行包含$2$或$4$个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间$[x,y]$内每个数加上$k$。

操作2：格式：2 x 含义：输出第x个数的值。

输出格式

输出包含若干行整数，即为所有操作2的结果。

INPUT & OUTPUT’s examples

Input’s eg #1

Output’s eg #1

1
2

6
10

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：$N \leq , M \leq 10$

对于70%的数据：$N \leq 10000,M \leq 10000$

对于100%的数据：$N \leq 500000,M \leq 500000$

样例说明

分析

看起来这道题似乎和树状数组的作用正好相反，那怎样用树状数组求解呢？

虽然可以用线段树一遍过，但是线段树码量辣么大，懒得写啊。

这时候，差分作为一个$O(n)$的优秀算法就体现出它的作用了。

在树状数组中我们可以用前$k$项的和来表示第$k$个数。

对于单点求值，直接进行printf("%d",Query(x))即可。

当我们需要对区间$[l,r]$进行修改的时候，仅需要在差分数组（这里我们用树状数组维护）l和r+1的位置上分别+v和-v即可。

我们用树状数组来维护差分的过程，对于每一次区间修改的操作，可以：

1
2
3

scanf("%d%d%lld",&l,&r,&v);
Update(l,v);
Update(r+1,-v);

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 5e5+7;
int n,m;
long long Tree[MAXN];
long long a[MAXN];
int op;
/* functions */
inline int lowbit(int x){
    return x&(-x);
}
inline void Update(int x,long long val){
    while(x<=n){
        Tree[x]+=val;
        x+=lowbit(x);
    }
}
inline long long Query(int k){
    long long ans=0;
    while(k){
        ans+=Tree[k];
        k-=lowbit(k);
    }
    return ans;
}
int main(int argc,char *argv[]){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        Update(i,a[i]-a[i-1]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            int l,r;
            long long v;
            scanf("%d%d%lld",&l,&r,&v);
            Update(l,v);
            Update(r+1,-v);
        }
        if(op==2){
            int p;
            scanf("%d",&p);
            printf("%lld\n",Query(p));
        }
    }
    return 0;
}

洛谷P3368题解