数据结构:树状数组

发布于:2024-07-11 ⋅ 阅读:(30) ⋅ 点赞:(0)

树状数组

基本操作:1.快速求前缀和 2.修改一个数。

基本图示:

 lowbit:求出一个数字二进制最后一个1的位置;

原理:

我们发现,除了最后一个1,以及其后面的0,其余位置都是反,则要求最后一位1的位置,可以将原码和补码按位&;而计算机中-x有取补码,则lowbit(x)=x&-x;

#define lowbit (x&(-x));

例子:数组:1,2,3,4,5,6,7

1.如果想要修改6=0110, 

 

则会影响0110对应的:用lowbit+操作就可以修改,即6处修改,6+2(lowbit(6)=2)=8,对8处修改

2.如果想要查询【2,5】之间的和,可以求sum(5)-sum(1)

 sum(5),5=0011,则用lowbit-就可以求出,sum加上5处的值,lowbit(5)=1,5-1=4,sum再加上4处的值,刚好就是sum(5),求出【2,5】,类似于前缀和,求出sum(5)-sum(1)。

综上所述:

1.单点修改

void upload(int x,int d){
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);
    }
}

2.区间查询

int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}

 一个典型题:

 

我们不难知道,如果想要求解此题,想要知道V(题中)只要知道第a_i个数,左边有m个比它大,右边有n个比它大,然后mn就是V的个数,\sum mn就是总的V图腾数,∧同理(左边,右边比它小)

     

然后利用树状数组就可以求解逆序对:

lower指比它大的数,Greater比它小的数。

第一遍求左边比它大(小)的数,第二遍(清空第一遍的tr,并逆序求一遍)求右边比它大(小)的数。

注:为啥会求出来,理由是每次更新树状数组, upload(y,1),则+1,之后遍历下一个数,就知道左边那群数比这个数大还是小的个数是多少(具体例子如下:)

1:for(int i=0;i<n;i++){
        int y=a[i];
        Greater[i]=sum(n)-sum(y);
        lower[i]=sum(y-1);
        upload(y,1);
    }
2: memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i -- )
    {
        int y=a[i];
        res1+=great[i]*(LL)(sum(n)-sum(y));
        res2+=lower[i]*(LL)(sum(y-1));
        upload(y,1);
    }

 

 左边是第一次,右边是逆序第二次(上面代码1与代码2对应)

 

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

using namespace std;

const int N=200010;
int tr[N];
typedef long long LL;
#define lowbit (x&(-x));
int n;
void upload(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int a[N],great[N],lower[N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for(int i=1;i<=n;i++){
        int y=a[i];
        great[i]=sum(n)-sum(y);//right
        lower[i]=sum(y-1);//left
        upload(y,1);
    }
    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i -- )
    {
        int y=a[i];
        res1+=great[i]*(LL)(sum(n)-sum(y));
        res2+=lower[i]*(LL)(sum(y-1));
        upload(y,1);
    }
    printf("%lld %lld\n", res1, res2);
    return 0;
}

3.区间修改,单点查询

利用差分数组:

 

详见差分性质 


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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr[N];

#define lowbit (x&(-x));

void upload(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
LL sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
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 ++ ) upload(i, a[i] - a[i - 1]);

    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if (*op == 'C')
        {
            scanf("%d%d", &r, &d);
            upload(l, d), upload(r + 1, -d);
        }
        else
        {
            printf("%lld\n", sum(l));
        }
    }

    return 0;
}

4.区间修改,区间查询

1.记录差分

   int b = a[i] - a[i - 1];

2.大致思路

如果要求区间修改,利用差分,同上。

但是,区间查询则需要利用一些数学推导:

其中,a为原数组,b为差分数组:

 总面积:(\sum_{i=1}^{x}b_i)*(x+1),减去黄色部分:\sum_{i=1}^{x} ib_i,则白色区域:(\sum_{i=1}^{x}b_i)*(x+1)-\sum_{i=1}^{x}ib_i

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和
区间查询:

prefix_sum(r)-prefix_sum(l-1))

区间修改:

 add(tr1, l, d), add(tr2, l, l * d);
 add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);

 总代码:

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和

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 += tr[i];
    return res;
}

LL prefix_sum(int 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++){
        int b=a[i]-a[i-1];
        add(tr1,i,b);
        add(tr2,i,(LL)b*i);
    }
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') {
            printf("%lld\n",prefix_sum(r)-prefix_sum(l-1));
        }
        else{
            scanf("%d", &d);
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }
    return 0;
}

5.应用:谜一样的牛

 这个题从正序入手不容易,可以从逆序入手。如何入手,可以举个例子:

 从h【4】=0开始,发现前面没有一个比它低,那么它最低,则是1。然后tree更新。

则发现,只要从最后一个开始,找到第h[i]+1个数就是它的位置,同时更新tree。

为了找到h[i]+1(其实就是求第k小的数,而tr数组记录了数组的前缀和,也就表示了数字到底是在数组中第几小),可以利用二分法。

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

using namespace std;
const int N=100010;
int n;
int h[N];
int tr[N];
int ans[N];
#define lowbit x&(-x);
void update(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)  cin>>h[i];
    for(int i=1;i<=n;i++) update(i,1);
    for(int i=n;i;i--){
        int k=h[i]+1;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(sum(mid)>=k) r=mid;
            else l=mid+1;
        }
        ans[i]=r;
        update(r,-1);
    }
    for (int i = 1; i <= n; i ++ ) printf("%d\n", ans[i]);
    return 0;
}