進階數據結構——樹狀數組

前言

看這篇文章前我建議你們先看這個視頻還有這個視頻，不然你們可能看不懂。
在這里插入圖片描述

一、樹狀數組的核心思想與本質

核心思想：樹狀數組（Fenwick Tree）是一種用于高效處理前綴和查詢和單點更新的數據結構。
本質：通過二進制索引和樹形結構，將前綴和的計算復雜度從

O(n) 優化到 O(logn)。

二、樹狀數組的基本操作

初始化
初始化一個大小為 n 的數組，所有元素初始值為 0。
單點更新
更新某個位置的值，并維護樹狀數組的結構。
前綴和查詢
查詢從第一個元素到某個位置的前綴和。
區間和查詢
查詢某個區間的和。

三、樹狀數組的應用場景

動態前綴和查詢：

實時查詢數組的前綴和，支持單點更新。

示例：LeetCode 307. 區域和檢索 - 數組可修改。

逆序對計數：

使用樹狀數組統計數組中逆序對的數量。

示例：LeetCode 493. 翻轉對。

區間更新與單點查詢：

通過差分數組和樹狀數組實現區間更新和單點查詢。

示例：LeetCode 370. 區間加法。

二維樹狀數組：

處理二維數組的前綴和查詢和單點更新。

示例：LeetCode 308. 二維區域和檢索 - 可變。

四、樹狀數組的復雜度分析
時間復雜度
單點更新：
O(logn)。

前綴和查詢：
O(logn)。

區間和查詢：
O(logn)。

空間復雜度
存儲樹狀數組：
O(n)。

五、樹狀數組的優化技巧

差分數組
通過差分數組實現區間更新和單點查詢。
離散化
在數據范圍較大時，使用離散化減少樹狀數組的大小。
多維擴展
將樹狀數組擴展到二維或更高維度，處理多維數組的前綴和查詢和單點更新。

六、常見誤區與調試技巧

誤區一：樹狀數組適用于所有區間查詢問題
澄清：樹狀數組適用于前綴和查詢和單點更新，對于復雜的區間查詢問題可能需要其他數據結構（如線段樹）。
誤區二：樹狀數組的初始化復雜度高
澄清：樹狀數組的初始化復雜度為 O(nlogn)，但可以通過線性初始化優化到 O(n)。
調試方法
打印樹狀數組：在每次操作后輸出樹狀數組的內容，檢查是否正確。

可視化樹結構：手動畫出樹狀數組的結構，模擬操作過程。

七、代碼模版

單點更新

例題【模板】樹狀數組 1

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowbit(int x);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx,T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowbit(int x) {return x & (-x);
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowbit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowbit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}int main() {int n, m;cin >> n >> m;FenwickTree<int> ft(n);for (int i = 1; i <= n; i++) {int x;cin >> x;ft.update(i, x);}while (m--) {int z, x, y;cin >> z >> x >> y;if (z == 1) {ft.update(x, y);}else {int sum = ft.query(x, y);cout << sum << endl;}}return 0;
}

區間更新

例題【模板】樹狀數組

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);void update(int idx, T val);T query(int idx);T query(int l, int r);
public:FenwickTree(int n):m_tree(n+2,0){}void updateInterval(int l, int r, T val);T queryIndex(int idx);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}template<class T>
void FenwickTree<T>::updateInterval(int l, int r, T val) {update(l, val);update(r + 1, -val);
}template<class T>
T FenwickTree<T>::queryIndex(int idx) {return query(idx);
}int main() {int n, m;cin >> n >> m;FenwickTree<int>ft(n);for (int i = 1; i <= n; i++) {int a;cin >> a;ft.updateInterval(i, i, a);}while (m--) {int opt;cin >> opt;if (opt == 1) {int l, r, x;cin >> l >> r >> x;ft.updateInterval(l, r, x);}else {int k;cin >> k;cout << ft.queryIndex(k) << endl;}}return 0;
}

八、經典例題

排序

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n, m;cin >> n;FenwickTree<long long>ft(maxn);for (int i = 0; i < n; i++) {cin >> a[i];}long long sum = 0;for (int i = n - 1; i >= 0; i--) {		//逆序遍歷數組看看后面有多少個比當前這個值小的個數，乘于它本身累加起來ft.update(a[i], 1);sum += (long long)ft.query(a[i] - 1) * a[i];	//求1~a[i]-1元素個數}cout << sum << endl;return 0;
}

逆序對的數量

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//樹狀數組的序號是從1開始，利用離散化給原數組每個值標記它的序號，也就是排序好它們的大小}long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);sum += ft.query(a[i] - 1);		//查詢1~a[i]-1的元素和，他要找的是比它本身小的個數}cout << sum << endl;return 0;
}

三元組個數

這題就是遍歷到的原數組的每一個元素用左邊比它小的個數乘于右邊比它大的個數，但是復雜度還是太高了，所以還得需要離散化數組，用樹狀數組記錄比它小或大的個數

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define mod 998244353
#define maxn 1000001
int a[maxn], lt[maxn];	//lt[i]表示小于a[i]的個數int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//樹狀數組的序號是從1開始，利用離散化給原數組每個值標記它的序號，也就是排序好它們的大小}for (int i = 0; i < n; i++) {ft.update(a[i], 1);lt[i] = ft.query(a[i] - 1);}ft = FenwickTree<int>(n);long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);int gt = ft.query(a[i] + 1, n);		//求出比a[i]大的個數sum += (long long)lt[i] * gt % mod;sum %= mod;		//sum這個值可能超出范圍所以還要取模}cout << sum << endl;return 0;
}