树状数组

class :vector<int>
{
    public:
        explicit (int k=0)
        {
            assign(k+1,0);//有效下标从1开始，0仅作逻辑用处
        }
        int lowbit(int k)
        {
            return k&-k;
            //也可写作x&(x^(x–1))
        }
        int sum(int k)//求第1个元素到第n个元素的和
        {
            return k>0?sum(k-lowbit(k))+(*this)[k]:0;
        }
        int last()//返回最后一个元素下标
        {
            return size()-1;
        }
        void add(int k,int w)//为节点k加上w
        {
            if(k>last())return;
            (*this)[k]+=w;
            add(k+lowbit(k),w);
        }
};

int n,m,i,num[100001],t[200001],l,r;//num:原数组；t：树状数组 
int lowbit(int x)
{
    return x&(-x);
}
void change(int x,int p)//将第x个数加p 
{
    while(x<=n)
    {
        t[x]+=p;
        x+=lowbit(x);
    }
    return;
}
int sum(int k)//前k个数的和 
{
    int ans=0;
    while(k>0)
    {
        ans+=t[k];
        k-=lowbit(k);
    }
    return ans;
}
int ask(int l,int r)//求l-r区间和 
{
    return sum(r)-sum(l-1); 
}