洛谷 P3368 【模板】树状数组 2

class FenwickTree{
public:
    FenwickTree(int sz): sz_(sz){
        ft_.resize(sz_);
    }

    FenwickTree(vector<long long>& f){
        sz_ = int(f.size());
        ft_.assign(sz_, 0);
        for (int i = 1; i < sz_; ++i){
            ft_[i] += f[i];
            if (i + lowbit(i) < sz_){
                ft_[i + lowbit(i)] += ft_[i];
            }
        }
    }

    FenwickTree(vector<int>& s){
        sz_ = *max_element(s.begin() + 1, s.end()) + 1;
        ft_.resize(sz_);
        for (size_t i = 1; i < s.size(); ++i){
            ft_[s[i]] ++;
            if (s[i] + lowbit(s[i]) < sz_){
                ft_[s[i] + lowbit(s[i])] += ft_[s[i]];
            }
        }
    }

    void update(int pos, long long value){
        while (pos < sz_){
            ft_[pos] += value;
            pos += lowbit(pos);
        }
    }

    void update(int l, int r, long long value){
        update(l, value);
        update(r + 1, -value);
    }

    long long query(int p){
        assert(p < sz_);
        long long res = 0;
        while (p > 0){
            res += ft_[p];
            p -= lowbit(p);
        }
        return res;
    }

    long long query(int l, int r){
        assert(l <= r);
        return query(r) - query(l - 1);
    }


private:
    int sz_;
    vector<long long> ft_;


private:
    inline int lowbit(int x) {return (x & (-x));}
};






void solve(){
    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    for (int i = n; i >= 1; --i){
        a[i] -= a[i - 1];
    }

    FenwickTree ft(a);
    while (m --){
        int t, x, y;
        cin >> t;
        if (t & 1){
            long long k;
            cin >> x >> y >> k;
            ft.update(x, y, k);
        }
        else{
            cin >> x;
            cout << ft.query(1, x) << '\n';
        }
    }
}