펜윅 트리

struct FenwickTree
{
    vector<int>tree;
    FenwickTree(int n){tree.resize(n+1,0);}
    int sum(int idx)
    {
        idx++;
        int ret=0;
        while(ret)
        {
            ret+=tree[idx];
            idx&=(idx-1);
        }
        return ret;
    }
    void add(int idx,int value)
    {
        idx++;
        while(idx<tree.size())
        {
            tree[idx]+=value;
            idx+=(idx&-idx);
        }
    }
    
};