ll BIT[N];
// ll xBIT[N];

void bit_add(int x, ll val) {
    for (int i=x; i<N; i+=i&-i) {
        BIT[i] += val;       
        // xBIT[i] += x*val;
        // 区间查询时 BIT[i] += val; xBIT[i] += x*val;
    }
}

ll bit_ps(int x) {
    ll rt = 0;
    for (int i=x; i>0; i-=i&-i) {
        rt += BIT[i];
        // rt += x*BIT[i]-xBIT[i];
        // 区间查询时 rt += (x+1)*BIT[i]-xBIT[i];
    }
    return rt;
}

//BIT 维护a
//单点修改：bit_add(x, val); 下标x增加val
//区间和：  bit_ps(y)-bit_ps(x-1); a[x...y]的区间和

// BIT 维护a的差分
//区间修改：bit_add(x, val); bit_add(y+1, -val) a[x...y]各增加val
//单点值： bit_ps(x);

// BIT 维护差分，间接维护a的前缀
//区间修改：bit_add(x, val), bit_add(y+1, -val); a[x...y]各增加val
//区间和：  bit_ps(y)-bit_ps(x-1); a[x...y]的区间和

/*
差分数组间接维护前缀数组原理
a 原数组，d 差分数组，p 前缀数组 
a[0] = d[0] = p[0] = 0

d[i] = a[i] - a[i-1]
a[i] = p[i] - p[i-1]

Σd[i] = a[n], i ∈[1,n]
Σa[i] = p[n], i ∈[1,n]
ΣΣd[j] = p[n], j ∈[1,i], i ∈[1,n]
p[n] = (n+1)Σd[i]-Σd[i]*i

*/

区间操作

数组

定义数组长度为n的a, 数组的存储索引从1到n，代码中a[0]=0 修改a的某个元素时间复杂度是O(1), 求区间和是O(n)。 求区间和可以求前缀和再做差。

差分数组

定义差分数组d[i] = a[i]-a[i-1] 那么： d[1] = a[1]

d[2] = a[2]-a[1]

d[3] = a[3]-a[2]

...

d[i] = a[i]-a[i-1]

...

d[n] = a[n]-a[n-1]

d[1]+d[2]+d[3]+...+d[i]+...+d[n] = a[n] 即$a[n] = \sum \limits_{i=1}^{n}d[i]$ 求d的前缀和就是a的一个元素。 单点修改d[r+1]-=val, d[l] +=val, 就可做到区间[l,r]每个元素增长val。 区间修改O(1), 单点查询O(n)

前缀数组

区间查询O(1)

$p[n] = \sum \limits_{i=1}^{n}a[i]， p[0] = 0$

树状数组

树状数组的功能，O(logn) 的时间复杂度让a[i]增加val，O(logn) 的时间复杂度求a[1...i]。1<=i<=n

如果用树状数组维护差分数组。那么区间修改O(logn), 单点查询O(logn)

如果要查询区间任然可以维护差分数组，不过要用差分数组来表示a的前缀数组。 p[n]-p[n-1] = a[n], a[n] = d[n]-d[n-1] $p[n] = \sum \limits_{i=1}^{n}a[i]$ $a[n] = \sum \limits_{i=1}^{n}d[i]$ $p[n] = \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{i}d[j] = \sum \limits_{i=1}^{n}(n+1-i)\times d[i] = (n+1)\sum \limits_{i=1}^{n} d[i] + \sum \limits_{i=1}^{n}i\times d[i]$