数据结构——树状数组

本文主要内容：

• 基础复习（单点修改和区间查询）
• 用树状数组实现区间修改和单点查询
• 用树状数组实现区间修改和区间查询
• 将输入数组值作为树状数组下标

1 基础复习

• 主要功能：

1. 动态实现数组的单点修改和区间查询

• 时间复杂度：

  单点修改和区间查询都是o(logn)

• 注意事项：

1. 变量值的溢出
2. 下标从1开始

• 模板题：Acwing1264. 动态求连续区间和

1.1 Acwing1264. 动态求连续区间和

#include<iostream>

using namespace std;

const int N = 1e5 + 5;

typedef long long LL;

int tr[N];
int n, m;
//lowbit函数
int lowbit(int x)
{
    return x & -x;
}
//单点修改函数
void add(int x, int delta)
{
    for(int i = x; i < N; i += lowbit(i))
        tr[i] += delta;
}
//前缀和查询函数
LL query(int x)
{
    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++)
    {
        int x;
        cin >> x;
        add(i, x);
    }
    while(m--)
    {
        int k, a, b;
        cin >> k >> a >> b;
        if(k == 0)cout << query(b) - query(a - 1) << endl;
        else add(a, b);
    }
    return 0;
}
           

2 用树状数组实现区间修改和单点查询

2.1 Acwing242. 一个简单的整数问题

• 思路：

1. 利用原数组a[]的差分数组b[]构建树状数组tr[]
2. 修改原数组区间[l, r]变为修改差分数组两个元素b[l]和b[r+1]
3. 查询元素组某个元素a[x]变为查询b[]前x的所有元素之和

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

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

int lowbit(int x)
{
    return x & -x;
}

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

LL query(int x)
{
    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]);
    }
    while(m--)
    {
        int l, r, d;
        char op;
        cin >> op;
        if(op == 'C')
        {
            cin >> l >> r >> d;
            add(l, d), add(r + 1, -d);
        }
        else
        {
            cin >> d;
            cout << query(d) << endl;
        }
    }
    return 0;
}
           

3 用树状数组实现区间修改和区间查询

3.1 Acwing243. 一个简单的整数问题2

• 思路：

1. 求s[k]等价于求a[1]+a[2]+…+a[k]等价于求b[1]+(b[1]+b[2])+…+(b[1]+b[2]+…+b[k])等价于求k*b[1]+(k-1)* b[2] + … + b[k]等价于求k*b[1]+k*b[2]+…+k*b[k]-(0*b[1]+1*b[2]+2*b[3]+…+(k-1)*b[k])
2. 利用原数组a[]的差分数b[]组构建一个树状数组tr1[]，解决区间修改问题
3. 利用b[]与元素下标减1的积构建一个树状数组tr2[]
4. 修改相应区间查询函数和单点修改函数，详情见代码

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

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

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int d)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        tr1[i] += d;
        tr2[i] += (LL)(x - 1) * d;
    }
}

LL query(int x)
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i))
    {
        res += (LL)x * tr1[i];
        res -= tr2[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]);
    }
    while(m--)
    {
        char op;
        int l, r, d;
        cin >> op;
        if(op == 'C')
        {
            cin >> l >> r >> d;
            add(l, d), add(r + 1, -d);
        }
        else
        {
            cin >> l >> r;
            cout << query(r) - query(l - 1) << endl;
        }
    }
    return 0;
}
           

4 将输入数组值作为树状数组下标

4.1 Acwing1215.小朋友排队

• 思路：

1. 每个小朋友需要交换的次数 = 排在他前面比他高的小朋友数+ 排在他后面且比他矮的小朋友数
2. 每读入一个身高h，求h处前缀和可得知有已经读取的小朋友中有多少个小朋友身高小于h，h处元素赋值1

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5, M = 1e6 + 5;

int h[N], cnt[N], tr[M];
int n;

int lowbit(int x)
{
    return x & -x;
}

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

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> h[i];
    for(int i = 1; i <= n; i++)
    {
        add(h[i]);
        cnt[i] += i - query(h[i]);
    }
    memset(tr, 0, sizeof tr);
    for(int i = n; i >= 1; i--)
    {
        add(h[i]);
        cnt[i] += query(h[i] - 1);//不包括自己
    }
    LL res = 0;
    for(int i = 1; i <= n; i++)
        res += (LL)cnt[i] * (cnt[i] + 1) / 2;
    cout << res;
    return 0;
}