单点修改,区间查询前缀和

单点修改

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  tr[i]+=c;
}

区间查询

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

区间修改,单点查询某个数——>tr[i]维护差分数组而不是原数组

差分数组求前缀和对应数组中某个元素的值
修改区间的值只需要修改端点差分数组的值
这两个操作正好适用于普通的树状数组的单点修改和区间查询
因此我们只需要用tr[i]来维护差分数组就可以了
242. 一个简单的整数问题

#include<iostream>
using namespace std;
const int N=100010;
int a[N],tr[N];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  tr[i]+=c;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        add(i,a[i]-a[i-1]);
    }
    for(int i=0;i<m;i++)
    {
        char c;
        cin>>c;
        if(c=='C')
        {
            int l,r,d;
            cin>>l>>r>>d;
            add(l,d),add(r+1,-d);
        }
        if(c=='Q')
        {
            int d;
            cin>>d;
            cout<<ask(d)<<endl;
        }
    }
}

区间修改,区间查询某个数

利用公式

AcWing 243. 一个简单的整数问题2

#include<iostream>
using namespace std;
const int N=100010;
typedef long long LL;
int n,m;
int a[N];
LL tr1[N],tr2[N];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,LL c,LL tr[])
{
    for(int i=x;i<=n;i+=lowbit(i))  tr[i]+=c;
}
LL ask(int x,LL tr[])
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        add(i,a[i]-a[i-1],tr1);
        add(i,(LL)(a[i]-a[i-1])*i,tr2);
    }
    while(m--)
    {
        char c;
        cin>>c;
        if(c=='Q')
        {
            int l,r;
            cin>>l>>r;
            cout<<ask(r,tr1)*(r+1)-ask(r,tr2)-ask(l-1,tr1)*l+ask(l-1,tr2)<<endl;
        }
        else{
            int l,r,d;
            cin>>l>>r>>d;
            add(l,d,tr1),add(r+1,-d,tr1);
            add(l,l*d,tr2),add(r+1,(r+1)*-d,tr2);
        }
    }
}

动态删除,区间查询第k大数——>tr[i]维护每个元素存在的次数,二分查询第k小

用树状数组维护每个数是否存在,存在即为1.那么tr[i]维护的就是(i-lowbit(i),i]中的有效数
通过前缀和可以查询到[0,x]中的有效数个数
因此只需要找到最小的x满足sum(x)>=k即可,此时这个x就是剩余数种第k小的数
AcWing 244. 谜一样的牛

#include<iostream>
using namespace std;
const int N=100010;
int tr[N],a[N],res[N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  tr[i]+=c;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)    cin>>a[i];
    for(int i=1;i<=n;i++)   tr[i]=lowbit(i);
    for(int i=n;i>=1;i--)
    {
        int l=0,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(ask(mid)>=a[i]+1) r=mid;
            else    l=mid+1;
        }
        res[i]=r;
        add(r,-1);
    }
    for(int i=1;i<=n;i++)   cout<<res[i]<<endl;

}