BIT區間加值

緒論

眾所周知，BIT能夠實現在$O(n)$空間下單點加值，並計算區間和。
至於區間加值則需要使用線段樹及lazy tag。
但線段樹code超長，debug很累，而且需要約$4n$的空間。

於是我們想要在BIT上實作區間加值，這有可能嗎?

答案是肯定的。

正文

差分

差分就是將序列中的每一項改為自己減去前一項之值，也就是說:

$g_i = f_i - f_{i - 1},if \space i >= 1$
$g_i = g_i,if \space i = 0$

於是乎，當我們要求$f_i$時，只需(?)求出$\displaystyle \sum_{k = 0}^{i} g_k$即可。
看起來畫蛇添足，但這在區間加值，單點查詢時很有用。

差分 + BIT?

BIT能夠在$O(\log n)$時間內完成單點修改、區間查詢。
而差分則能夠在$O(1)$時間內完成區間加值、$O(n)$時間內完成單點查詢。

於是乎，我們將兩者合併。

g[]為差分序列
f[]為原序列

$\displaystyle \sum_{k = 0}^b f_k = \sum_{k = 0}^b g_k \cdot (b + 1 - k) = [(b + 2) \cdot \sum_{k = 0}^b g_i] - [\sum_{k = 0}^b g_i \cdot (k + 1)]$

所以，我們維護兩顆BIT，分別儲存g[]及$g_i \cdot (i + 1)$即可做到$O(\log n)$完成區間加值、區間查詢了

例題

code

// Author : ysh
// 12/07/2022 Wed 12:54:30.08
#include<bits/stdc++.h>
using namespace std;
struct tree{
    vector<long long>f;
    int n;

    tree(vector<long long>&f) {
        this->n = f.size();
        this->f.resize(n);
        for(int i = 0,len = f.size();i<len;i++) {
            add(i,f.at(i));
        }
    }

    void add(int a,long long b) {
        for(;a < n;a = (a | (a + 1))) {
            f.at(a) += b;
        }
        return;
    }

    long long sum(int a) {
        long long ans = 0;
        for(;a >= 0;a = (a & (a + 1)) - 1) {
            ans = ans + f.at(a);
        }
        return ans;
    }

    long long sum(int a,int b) {
        if(a > b) swap(a,b);
        return sum(min(n - 1,b)) - sum(a - 1);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<long long>f(n + 1);
    long long last = 0;
    for(int i = 1;i<=n;i++) {
        cin>>f.at(i);
        swap(last,f.at(i));
        f.at(i) = last - f.at(i);
    }
    vector<long long>g(n + 1);
    for(int i = 1;i<=n;i++) {
        g.at(i) = f.at(i) * (i);
    }
    tree a(f),b(g);
    int m;cin>>m;
    while(m--) {
        int aa,bb;cin>>aa>>bb;
        if(aa == 2) {
            int c;cin>>c;
            cout<<(a.sum(1,c) * (c + 1) - b.sum(1,c)) - (a.sum(1,bb - 1) * (bb) - b.sum(1,bb - 1))<<"\n";
        }
        if(aa == 1) {
            int c,d;cin>>c>>d;
            a.add(bb,d);
            if(c != n) a.add(c + 1,-d);
            b.add(bb,d * bb);
            if(c != n) b.add(c + 1,-d * (c + 1));
        }
    }
    return 0;
}