树状数组及其拓展

作用：

 

 查询应该是res+=tr[i]

目录

1.楼兰图腾

2.一个简单的整数问题（差分）

3.一个简单的整数问题2（差分+分析）

4.谜一样的牛（二分查找）

---

1.楼兰图腾

tr表示这个位置有多少个这个数

241. 楼兰图腾 - AcWing题库

#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
int tr[N],a[N];
ll up[N],down[N];//up记录上升的有多少个数，down记录下降的有多少个数
int lowbit(int x)//lowbit运算
{
    return x&-x;
}
void add(int x,int c)//某个位置加一个数的操作
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)//算前x个的和
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;iscanf("%d",&a[i]);
    //一开始tr是0，啥也没有一个数都没有
    for(int i=0;i
    {
        int y=a[i];
        up[i]=sum(n)-sum(y);//表示目前为止，0~i位置有多少个数是大于大于y的
        down[i]=sum(y-1);//表示目前为止，0~i位置有多少个数是小于y的
        add(y,1);//该位置添加个y
    }
    ll res1=0,res2=0;
    //现在的tr是已经弄到了整个序列的数了
    for(int i=0;i
    {
        int y=a[i];
        res1+=up[i]*(ll)(sum(n)-sum(y));//答案就是左边大于y的数乘以右边大于y的数
        res2+=down[i]*sum(y-1);//答案就是左边小于y的数乘以右边小于y的数
        add(y,-1);//把这个数去掉，不然待会算右边会算到这个数，实际是这个数已经用过了
    }
    printf("%lld %lld\n",res1,res2);
    return 0;
}

2.一个简单的整数问题（差分）

242. 一个简单的整数问题 - AcWing题库

把tr数组当成差分数组即可

假如[l,r]+c,则b[l]+=c,b[r+1]-=c;

假如求x的数是多少，相当于求b[x]的前缀和，然后可以直接用树状数组求用sum(x)即可

#include
using namespace std;
const int N=1e5+10;
int n,m;
int tr[N],a[N];//tr就是差分数列
int lowbit(int x)//lowbit运算
{
    return x&-x;
}
void add(int x,int c)//某个位置加一个数的操作
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)//求前x项和
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);//让tr是a[i]的差分，则b[i]=a[i]-a[i-1]
    while(m--)
    {
        char str[2];
        scanf("%s",str);
        if(str[0]=='Q')
        {
            int op;
            scanf("%d",&op);
            printf("%d\n",sum(op));//输出前op项和
        }
        else
        {
            int l,r,c;
            scanf("%d%d%d",&l,&r,&c);
            add(l,c),add(r+1,-c);//差分，b[l]+=c,b[r+1]-=c
        }
    }
    return 0;
}

3.一个简单的整数问题2（差分+分析）

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

弄两个树状数组，其中一个是差分数组b[i]，另一个是i*b[i]

 

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
int a[N];
ll tr1[N],tr2[N];//tr1记录的是b[i],tr2是i*b[i]
int lowbit(int x)//lowbit运算
{
    return x&-x;
}
void add(ll tr[],int x,ll c)//某个树状数组的加数
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
ll sum(ll tr[],int x)//某个树状数组的求前缀和
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
ll ans(int x)//求总数组的前x项的和
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(tr1,i,a[i]-a[i-1]),add(tr2,i,(ll)i*(a[i]-a[i-1]));//初始化初始值
    while(m--)
    {
        char op[2];
        int l,r,c;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='Q') printf("%lld\n",ans(r)-ans(l-1));//求l~r的和，也就是1~r的和减去1~l的和
        else
        {
            scanf("%d",&c);
            //b[l]+=c
            add(tr1,l,c),add(tr2,l,l*c);
            //b[r+1]-=c;
            add(tr1,r+1,-c),add(tr2,r+1,(ll)-c*(r+1));
        }
    }
    return 0;
}

4.谜一样的牛（二分查找）

244. 谜一样的牛 - AcWing题库

思路：从n往1看，每次给剩余的数里面第a[i]+1小的数，然后把这个数删掉，一直这样操作即可

找第a[i]+1小的数:

1.把每个数初始值为1，表明这个数还没用过，每个前缀和表明了当前数是第几小的数

2.二分查找第a[i]+1小的数，因为每个数的前缀和是递增的可以二分

#include
using namespace std;
const int N=1e5+10;
int n;
int a[N],tr[N],ans[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 sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,1);//初始化初始值,让每个数都为1，表明没有用过
    for(int i=n;i;i--)
    {
        int b=a[i]+1;//找第a[i]+1小的数
        int l=1,r=n;
        while(l//二分
        {
            int mid=l+r>>1;
            if(sum(mid)>=b) r=mid;//假如前缀和大了，说明当前数不是第b小的数
            else l=mid+1;
        }
        ans[i]=l;//让答案等于当前找到的第b小的数
        add(l,-1);//把当前数删除，因为已经用过了
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}