??個人主頁：為夢而生~ 關(guān)注我一起學(xué)習(xí)吧！
??專欄：算法題、 基礎(chǔ)算法、數(shù)據(jù)結(jié)構(gòu)~趕緊來學(xué)算法吧
??往期推薦：
【算法基礎(chǔ) & 數(shù)學(xué)】快速冪求逆元（逆元、擴展歐幾里得定理、小費馬定理）
【算法基礎(chǔ)】深搜
數(shù)據(jù)結(jié)構(gòu)各內(nèi)部排序算法總結(jié)對比及動圖演示（插入排序、冒泡和快速排序、選擇排序、堆排序、歸并排序和基數(shù)排序等）
【算法 & 高級數(shù)據(jù)結(jié)構(gòu)】樹狀數(shù)組：一種高效的數(shù)據(jù)結(jié)構(gòu)（一）

上一篇文章我們介紹了樹狀數(shù)組這個數(shù)據(jù)結(jié)構(gòu)，并且進行了其原理的數(shù)學(xué)推導(dǎo)，這篇文章基于上一篇文章，來講一下這個數(shù)據(jù)結(jié)構(gòu)在算法題中的應(yīng)用

還不知道樹狀數(shù)組是什么的來看這篇文章：【算法 & 高級數(shù)據(jù)結(jié)構(gòu)】樹狀數(shù)組：一種高效的數(shù)據(jù)結(jié)構(gòu)（一）

題目來源：AcWing

0 通用模板

首先，通用模板先擺上

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

1 單點修改，區(qū)間求和

• 例題：
  

輸入格式
第一行一個數(shù) $n$。

第二行是 $n$
個數(shù)，分別代表 。

輸出格式
兩個數(shù)，中間用空格隔開，依次為 V 的個數(shù)和 ∧ 的個數(shù)。

數(shù)據(jù)范圍
對于所有數(shù)據(jù)，$n\le 200000$，且輸出答案不會超過 int64。
$y_1～y_n$ 是 $1$到 $n$ 的一個排列。

輸入樣例：

5
1 5 3 2 4

輸出樣例：

3 4

• 主要思路：

因為兩個符號的特點對應(yīng)的每個點的縱坐標有這樣的特點： V 意味著兩邊點的縱坐標高于當前點的縱坐標， ∧ 意味著兩邊的縱坐標小于當前的縱坐標。所以我們只需要遍歷兩次數(shù)組，記錄每個點左右高于或低于當前點的縱坐標的點的數(shù)量，然后利用排列組合，計算出總數(shù)。

以下題解來源：https://www.acwing.com/solution/content/13818/

1. 從左向右依次遍歷每個數(shù)a[i]，使用樹狀數(shù)組統(tǒng)計在i位置之前所有比a[i]大的數(shù)的個數(shù)、以及比a[i]小的數(shù)的個數(shù)。
   統(tǒng)計完成后，將a[i]加入到樹狀數(shù)組。
2. 從右向左依次遍歷每個數(shù)a[i]，使用樹狀數(shù)組統(tǒng)計在i位置之后所有比a[i]大的數(shù)的個數(shù)、以及比a[i]小的數(shù)的個數(shù)。
   統(tǒng)計完成后，將a[i]加入到樹狀數(shù)組。

• 代碼：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 200010;
int n;
int a[N], tr[N];
int Greater[N], Lower[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(){
    cin >> n;
    
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    //將區(qū)間分成n份，看每一份左邊有多少個大于它和小于它的
    for(int i = 1; i <= n; i++){
        int y = a[i];
        Greater[i] = sum(n) - sum(y);
        Lower[i] = sum(y - 1);
        add(y, 1);
    }
    
    //memset一下tr數(shù)組，倒著求每一份右邊有多少個小于和大于它的
    memset(tr, 0, sizeof(tr));
    LL res1 = 0, res2 = 0;
    for(int i = n; i; i--){
        int y = a[i];
        res1 += Greater[i] * (LL)(sum(n) - sum(y));
        res2 += Lower[i] * (LL)sum(y - 1);
        add(y, 1);
    }
    
    cout << res1 << " " << res2 << endl;
    
    return 0;
}

2 區(qū)間增減，單點查詢

主要思想：建立差分數(shù)組

• 例題：

數(shù)據(jù)范圍
$1\le N,M\le 10^5,$
$|d|\le 10000,$
$|A[i]|\le 10^9$

輸入樣例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

輸出樣例：

4
1
2
5

• 主要思路：

樹狀數(shù)組每次修改對應(yīng)的是某個范圍的前綴和的值的修改，所以如果需要在大數(shù)據(jù)量的情況下進行區(qū)間修改操作，大概率會TLE的。

但是我們想到，區(qū)間操作我們可以利用最基礎(chǔ)的差分，使得區(qū)間操作優(yōu)化成$O(1)$的復(fù)雜度。

可以看到，將題目在原始組上的操作，轉(zhuǎn)換到差分數(shù)組上，和樹狀數(shù)組解決的問題一致。

• 代碼：

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;
int tr[N], a[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;
}

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

3 區(qū)間增減，區(qū)間求和

主要思想：建立差分數(shù)組+公式

• 例題：

數(shù)據(jù)范圍
$1\le N,M\le 10^5,$
$|d|\le 10000,$
$|A[i]|\le 10^9$

輸入樣例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

輸出樣例：

4
55
9
15

• 主要思想：

上一個應(yīng)用雖然利用差分數(shù)組解決了區(qū)間操作的問題，但是區(qū)間操作完之后，利用差分數(shù)組不利于進行區(qū)間查詢，所以需要進行一些推導(dǎo)，看看有什么性質(zhì)可以利用。

數(shù)學(xué)推導(dǎo)見如下題解：https://www.acwing.com/solution/content/44886/
因此只需維護兩個樹狀數(shù)組即可
一個是差分數(shù)組d[i]的樹狀數(shù)組tr[i]，還有一個是i*d[i]的樹狀數(shù)組tri[i]文章來源地址http://www.zghlxwxcb.cn/news/detail-843478.html

• 代碼：

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;
int a[N];   
LL tr1[N], tr2[N];  //tr1[i] : b[i]的前綴和  tr2[i] : i * b[i]的前綴和
int n, m;

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 quary(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 quary(tr1, x) * (LL)(x + 1) - quary(tr2, x);
}

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        int b = a[i] - a[i - 1];
        add(tr1, i, (LL)b);
        add(tr2, i, (LL)i * b);
    }
    
    while(m--){
        char op;
        cin >> op;
        
        if(op == 'C'){
            int l, r, d;
            cin >> l >> r >> d;
            add(tr1, l, (LL)d), add(tr1, r + 1, (LL)-d);
            add(tr2, l, (LL)l * d), add(tr2, r + 1, (LL)(r + 1) * -d);
        }else{
            int l, r;
            cin >> l >> r;
            cout << prefix_sum(r) - prefix_sum(l - 1) << endl;
        }
    }
    
    
    return 0;
}

到了這里，關(guān)于【算法 & 高級數(shù)據(jù)結(jié)構(gòu)】樹狀數(shù)組：一種高效的數(shù)據(jù)結(jié)構(gòu)（二）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！