区間加算・区間sum imos法 $O(log n)$

[Astral-23]

平衡二分木を書きませんか

template <typename T> struct sparse_static_sum {

    vector<ll> xs;
    vector<array<ll, 3>> adds;
    vector<T> S; // S[i] :=  [-∞, xs[i]] の累積和
    vector<T> fs; // fs[i] := [xs[i], xs[i+1]) の傾き
    bool f = false;
    int n;

    sparse_static_sum() {}

    private:

    int id(ll x) {
        int res = upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
        return res;
    }

    public: 

    void add(ll l, ll r, T x) { // [l, r) に一様に x加算
        xs.push_back(l);
        xs.push_back(r);
        adds.push_back({l, r, x});
    }

    void build() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        f = true;
        S.resize(n, 0);
        fs.resize(n ,0);

        for (auto [l, r, x] : adds) {
            fs[id(l)] += x;
            fs[id(r)] -= x;
        }
        for(int i = 0; i < n - 1; i++) {
            fs[i + 1] += fs[i];
        }
        for(int i = 0; i < n; i++) {
            S[i] = fs[i];
            if(i) S[i] += S[i-1] + fs[i-1] * (xs[i] - xs[i-1] - 1);
        }
    }

    T sum(ll r) { //[-∞, x)の和
        assert(f);
        r--;
        int nr = id(r);
        if(nr < 0) return T();
        T res = S[nr];
        res += (r - xs[nr]) * fs[nr];
        return res;
    }

    T prod(ll l, ll r) { return sum(r) - sum(l); } //[l, r) の和

    T get(ll i) { // [i]の値
        return prod(i, i + 1);
    }
};

https://atcoder.jp/contests/abc365/submissions/56319552

[Astral-23]

テスト

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <typename T> struct sparse_static_sum {

    vector<T> xs;
    vector<array<ll, 3>> adds;
    vector<T> S; // S[i] :=  [-∞, xs[i]] の累積和
    vector<T> fs; // fs[i] := [xs[i], xs[i+1]) の傾き
    bool f = false;
    int n;

    sparse_static_sum() {}

    private:

    int id(T x) {
        int res = upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
        return res;
    }

    public: 

    void add(T l, T r, T x) { // [l, r) に一様に x加算
        xs.push_back(l);
        xs.push_back(r);
        adds.push_back({l, r, x});
    }

    void build() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        f = true;
        S.resize(n, 0);
        fs.resize(n ,0);

        for (auto [l, r, x] : adds) {
            fs[id(l)] += x;
            fs[id(r)] -= x;
        }
        for(int i = 0; i < n - 1; i++) {
            fs[i + 1] += fs[i];
        }
        for(int i = 0; i < n; i++) {
            S[i] = fs[i];
            if(i) S[i] += S[i-1] + fs[i-1] * (xs[i] - xs[i-1] - 1);
        }
    }

    T sum(T r) { //[-∞, x)の和
        assert(f);
        r--;
        int nr = id(r);
        if(nr < 0) return T();
        T res = S[nr];
        res += (r - xs[nr]) * fs[nr];
        return res;
    }

    T prod(T l, T r) { return sum(r) - sum(l); } //[l, r) の和

    T get(int i) { // [i]の値
        return prod(i, i + 1);
    }
};

int main() {

    int test_case_size = 1000;
    while(test_case_size--) {
        int n = 1000;
        sparse_static_sum<ll> sts;
        vector<ll> A(n, 0);

        int q = 10000;
        while(q--) {
            int l = rand() % n;
            int r = rand() % n;
            int x = rand() % n;
            if(l > r) swap(l , r);
            for(int i = l; i < r; i++) {
                A[i] += x;
            }
            sts.add(l, r, x);
        }

        sts.build();

        for(int i = 0; i < n; i++) {
            assert(sts.get(i) == A[i]);
        }
    }

}```