树状数组_v2

树状数组模板整理。

树状数组

线段树下位，优点是处理简单问题常数小，好写。

struct FenwickTree{
    int n;
    vector<int>bit;
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void update(int p, int v){
        while(p <= n){
            bit[p] += v;
            p += p & (-p);
        }
    }

    int query(int p){
        int sum = 0;
        while(p > 0){
            sum += bit[p];
            p -= p & (-p);
        }
        return sum;
    }
};