資料結構——樹狀數組

本文主要内容：

• 基礎複習（單點修改和區間查詢）
• 用樹狀數組實作區間修改和單點查詢
• 用樹狀數組實作區間修改和區間查詢
• 将輸入數組值作為樹狀數組下标

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;
}