树状数组

树状数组所维护的数组记为\(a\)，\(n\)表示\(a\)中元素个数，\(lowbit(i)\)表示最低位\(1\)和后面所有\(0\)组成的数，\(c[i]\)表示\(a\)区间\([i - lowbit(i) + 1, i]\)的和。

\(add(k, x)\)：单点修改，表示\(a[k]=a[k]+x\)，时间复杂度：\(O(logn)\)。

\(sum\)：区间查询，\(sum(k)\)表示\(a\)区间\([1, k]\)的和，\(sum(l, r)\)表示区间\([l,r]\)的和，时间复杂度：\(O(logn)\)。

\(kth(k)\)：求第\(k\)小的数，\(a\)应为权值数组，即\(a[i]\)表示数\(i\)出现的次数，此时树状数组为权值树状数组，时间复杂度：\(O(logn)\)。

template <typename T>
class Fenwick 
{
private:
    int n;
    std::vector<T> c;
    #define lowbit(x) (x & -x)
public:
    Fenwick(int n) : n(n - 1), c(n) {}
    
    void add(int k, T x)
    {
        for (int i = k; i <= n; i += lowbit(i)) c[i] += x;
    }
    
    T sum(int k)
    {
        T sum = T();
        for (int i = k; i; i -= lowbit(i)) sum += c[i];
        return sum;
    }
    
    T sum(int l, int r) 
    {
        return sum(r) - sum(l - 1);
    }

    int kth(T k)
    {
        int x = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) 
            if (x + i <= n && k > c[x + i]) 
                x += i, k -= c[x];    
        return x + 1;
    }
};