一、介绍

功能

• 快速求前缀和 O(logn)
• 修改某一个数 O(logn)

原理

c[x]:以x结尾的长度lowbit(x)的所有数的和

父节点找所有子节点(求和操作)：c[x] = a[x] + c[x-1] + ... + c[lowbit(x-1)]，x为偶数时，每一次去掉最后一个1；x为奇数时，没有子节点
子节点找父节点(修改操作)：p = x + lowbit(x)，修改当前结点时，一连串的与该结点有关的父节点都要被修改

建立

题目

241. 楼兰图腾

思路：个数统计+树状数组(O(nlogn))

• y1~yn是1到n的一个全排列，对于某个位置的数而言，左边比它大的数的个数与右边比它大的数的个数的乘积就是组成'V'型的个数。
• 同理，左边比它小的数的个数与右边比它小的数的个数的乘积就是组成'^'型的个数。
• 因此，我们可以维护一个lower和upper数组，lower[i]表示比a[i]小的个数，upper[i]表示比a[i]大的个数。从左到右，边统计边查询，这样lower和upper就表示某个数左边比它大或小的数的个数。使用树状数组可以快速求出某个区间的和与修改某个数，c[x]来表示x出现的次数，sum(n)-sum(x)表示比x大的数的个数，sum(x-1)表示小于x的数的个数。
• 同理，从右往左边统计边查询，可以处理处某个数右边比它大或小的数的个数。

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 2e5 + 20;
int n;
int a[N];
int tr[N];
int lower[N],upper[N];

inline 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;
    }
}
LL sum(int x)
{
    LL res = 0;
    for(int i = x;i;i-=lowbit(i))
    {
        res += (LL)tr[i];
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1;i<=n;i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
    {
        int x = a[i];
        upper[i] = sum(n) - sum(x-1);//查询左边比a[i]大的数的个数
        lower[i] = sum(x-1);//查询左边比a[i]小的数的个数
        add(x,1);//添加a[i]
    }
    
    LL ans1 = 0,ans2 = 0;
    memset(tr,0,sizeof tr); //清空线段树
    for(int i = n;i>=1;i--)//从右往左求右边比a[i]大 or 小的数
    {
        int x = a[i];
        ans1 += (LL)upper[i]*(sum(n) - sum(x));//左边大的乘以右边大的就是构成V的个数
        ans2 += (LL)lower[i]*sum(x-1);//左边小的乘以右边小的就是构成^的个数
        add(x,1);//添加a[i]
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}

242. 一个简单的整数问题

思路：树状差分数组 O(nlogn)

• 题目中有区间修改，单点查询，符合差分数组的性质，而差分单点查询本质操作是求前缀和(O(n))，一定超时，因为差分的区间修改本质是单点修改，我们可以把差分数组构造成树状数组，使得所有操作为O(logn)的

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int 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 sum(int x)
{
    int res = 0;
    for(int i = x;i;i-=lowbit(i))
    {
        res += tr[i];
    }
    return res;
}
void insert(int l,int r,int c) //差分的插入操作均为单点修改，符合树状数组的性质
{
    add(l,c);// tr[l] += c;
    add(r+1,-c); //tr[r+1] -= c;
    return;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        insert(i,i,x);
    }
    while (m -- )
    {
        char op[2];
        int l,r,d,x;
        scanf("%s", &op);
        if(op[0] == 'C')
        {
            scanf("%d%d%d", &l, &r,&d);
            insert(l,r,d);
        }
        else
        {
            scanf("%d", &x);
            cout<<sum(x)<<endl;//通过差分还原某个数的操作是区间求和，符合树状数组性质
        }
    }
    return 0;
}

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

思路

• 题目中有区间修改，必须使用差分数组；有区间求和，必须使用树状数组
• 原数组的区间和相当于先对差分数组1~i求和还原出原数组，再对原数组求和，O(n^2)一定会超时
• 我们发现了对原数组1~n求和的公式(n+1)*(a1+…+an) - (1*a1+…n*an),因此我们可以构造两个树状数组分别维护ai与i*ai的差分

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

int n,m;
LL tr1[N],tr2[N];

int lowbit(int x)
{
    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 += (LL)tr[i];
    }
    return res;
}
void insert(int l,int r,LL c) //差分数组区间修改
{
    add(tr1,l,c);
    add(tr1,r+1,-c);
    add(tr2,l,l*c);
    add(tr2,r+1,-(r+1)*c);
}
LL get(int x) //求和公式
{
    LL res = (LL)(x+1)*sum(tr1,x)-sum(tr2,x);
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i<=n;i++)
    {
        int x;
        scanf("%d", &x);
        insert(i,i,x);
    }
    while (m -- )
    {
        char op[2];
        int l,r,d;
        scanf("%s", op);
        if(op[0] == 'C')
        {
            scanf("%d%d%d", &l,&r,&d);
            insert(l,r,d);
        }
        else
        {
            scanf("%d%d", &l,&r);
            cout<< get(r) - get(l-1) <<endl;
        }
    }
    return 0;
}

244. 谜一样的牛

思路：树状数组+二分 O(n(logn)^2)

先思考常规做法：数组A[i]表示前面有A[i]个数小于第i个位置的数，而A[i]是1-n的全排列，故我们可以A[i]从右往左遍历，对于第i个数而言，前i-1个数中有a[i]个比它小，即在这剩余的数中它是第a[i]+1小的，排序选出第a[i]+1个小的数，并从剩余的数中删除。时间复杂度为O(n^2logn)，显然不符合要求。
树状数组优化：tr[i]表示当前i的个数(0 or 1)，从右向左，二分查找出最小的x，使得sum[x]=a[i]+1，sum[x]表示1-x中有多少个剩余的数可用，因为是最小的x，所以tr[x]一定是1,且x一定是1-x中第a[i]+1小的数。x即为所求。最后一定要从tr中删除x

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N],n;
int tr[N];//tr[x]:表示当前x的可用的个数
int 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;
    }
    return;
}
int sum(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++) //注意从2开始循环
    {
        cin>>a[i];
    }
    for(int i = 1;i<=n;i++) add(i,1); //初始化为1，可用
    for(int i = n;i;i--)
    {
        int l = 1,r = n,x = a[i] + 1;
        while(l<r) //二分找出最小的x，使得sum(x) = a[i] + 1
        {
            int mid = l+r>>1;
            if(sum(mid) >= x) r = mid;
            else l = mid + 1;
        }
        ans[i] = r;
        add(r,-1); //删除x
    }
    for (int i = 1; i <= n; i ++ ) cout<<ans[i]<<endl;
    return 0;
}