Binary-Index-Tree

注意!!!:这不是树状数组的详解,而是利用树状数组做区间修改的方法,当然能区间修改了也能单点修改

先来个简单的树状数组啊
功能:

• 单点更新
• 区间查询(单点查询也就是特殊的区间查询啦)

    int n;
    int a[100005];
    void add(int x,int id){//id的位置上的数加上x
        while(id<=n){
            a[id]+=x;
            id+=id&(-id);
        }
        return ;
    }
    int query(int id){//id位置的前缀和
        int ans=0;
        while(id){
            ans+=a[id];
            id-=id&(-id);
        }
        return ans;
    }

以前想区间更新的时候就要跑去写线段树了

但现在有了差分这种思想,就可以用树状数组去区间更新啦

我们对原数列 $[1,n]$[1,n]进行一些操作啊
$d_i=a_i-a_{i-1}(a_0=0)$di​=ai​−ai−1​(a0​=0)
那么
$a_x=\sum _{i=1}^x{d}_i$ax​=i=1∑x​di​
又可得
$\sum _{i=1}^x{a}_i=\sum _{i=1}^x\sum _{j=1}^i{d}_j=\sum _{i=1}^x(x-i+1)d_i$i=1∑x​ai​=i=1∑x​j=1∑i​dj​=i=1∑x​(x−i+1)di​
显然(滑稽)
$\sum _{i=1}^x{a}_i=(x+1)\sum _{i=1}^x{d}_i-\sum _{i=1}^x{d}_i\ast i$i=1∑x​ai​=(x+1)i=1∑x​di​−i=1∑x​di​∗i
也可以
$\sum _{i=1}^x{a}_i=x\times \sum _{i=1}^x{d}_i-\sum _{i=1}^x{d}_i\ast (i-1)$i=1∑x​ai​=x×i=1∑x​di​−i=1∑x​di​∗(i−1)

所以这种要维护两个数组,一个维护 $d_i$di​和一个 $d_i$di​ $\ast$∗ $i$i
快点进正题啊,怎么区间修改啊,我等不及了
进正题,区间修改就用到差分的性质了,先来康康这个式子
$a_x=\sum _{i=1}^x{d}_i$ax​=i=1∑x​di​
假设在区间 $[L,R]$[L,R]加 $num$num我们是不是只要在 $d_L$dL​加上 $num$num,在 $R+1$R+1上减去num.(没看懂的,自己想一下,很简单的啦)笔者出来挨锤
抛个板子,逃了逃了,怕挨锤

 struct BIT{
    long long a1[N],a2[N];
    int n;
    inline int lowbit(int x){
        return x&-x;
    }
    void init(int _n){
        n=_n+1;
        for(int i=0;i<=n;i++){
            a1[i]=0;
            a2[i]=0;
        }
    }
    void add(int x,int y){
        for(int i=x;i<=n;i+=lowbit(i)){
            a1[i]+=y;
            a2[i]+=1ll*x*y;
        }
    }
    void lradd(int l,int r,int x){
        add(l,x);
        add(r+1,-x);
    }
    long long sum(int x){
        long long ans=0;
        for(int i=x;i;i-=lowbit(i)){
            ans+=1ll*(x+1)*a1[i]-a2[i];
        }
        return ans;
    }
    long long lrsum(int l,int r){
        return sum(r)-sum(l-1);
    }
}bits;