| 😊 | Powered By HeartFireY | Weighted Segment Tree |
一、權值線段樹 簡介
1.線段樹
線段樹是一種用于維護區間資訊的高效資料結構，可以在
線段樹維護的資訊必須滿足可加性，即能以可以接受的速度合并資訊和修改資訊，包括在使用Lazy标記時，标記也要滿足可加性
具體有關線段樹的的講解請參考部落格：線段樹 詳解與模闆
2.權值線段樹
權值線段樹是一種建立在基本線段樹之上的資料結構。是以它的基本原理仍是基于對區間的維護操作。但與線段樹相區分的點是：權值線段樹維護的資訊與基本線段樹有所差異：
- 基本線段樹中每個系欸但用來維護一段區間的最大值或總和等；
- 權值線段樹每個結點維護的是一個區間的數出現的次數。
實際上，權值線段樹可以看作是一個桶，桶的操作它都支援，并且能夠以更快的方式去完成。
根據權值線段樹的性質，我們可以知道其主要用途：
權值線段樹一般用于維護一段區間的數出現的次數，從它的定義來看，它可以快速計算出一段區間的數的出現次數。
在實際應用中，我們使用權值線段樹查詢區間第大的值。
二、權值線段樹的基本原理與操作
1.權值線段樹維護資訊的原理
基礎線段樹和權值線段樹的一個較大的差別點在于：(此處特指使用數組儲存樹結構)基礎線段樹根據初始的一個序列建立樹結構，具有單獨的建樹操作；而權值線段樹不需要進行建樹操作，初始狀态下預設建立一棵所有點權為的空樹，對于每個元素，在周遊的時候相應的結點做自增運算。換而言之：
- 權值線段是一棵已經建好的線段樹，儲存樹結構的下标範圍根據區間最大值最小值确定(一般開大空間即可)；
- 初始狀态下所有的點權均為；
- 執行插入元素的操作時，會導緻插入值對應的，同時引發單點更新操作。
- 可以從上述描述中得到基本推論：向空的權值線段樹中插入一個無序序列，則插入完成後在樹上無法再得到原序列的周遊，但能通過周遊得到有序序列(無序序列變有序序列)
我們可以通過結構對比線段樹與權值線段樹的差別，以此了解原理。
我們給定序列，以該序列為例建立兩種線段樹。
首先，序列長度為，建立基礎區間和查詢線段樹，結構圖如下：
對應具體的細節不再闡述。我們繼續建立權值線段樹：首先給出一棵空樹：
(注：為示範友善，A數組下标做+1操作，樹上的範圍也對應變化，這裡懶得改了~)
然後按照序列順序插入元素：
解釋：
：原序列中存在值為的元素個
：原序列中存在值為的元素個
：原序列中存在值為的元素個
：原序列中存在值為的元素個
：一定區間内所含元素的個數
我們繼續探究查找第大元素的方法：
由于權值線段樹每個節點記錄了某段區間内包含的元素個數，且元素在葉子節點構成的序列中是有序的：
- 對于整列數中第大/小的值，我們從根節點開始判斷（這裡按第大為例），如果比右兒子大，就說明第大的數在左兒子所表示的值域中。然後，要減去右兒子。（這是因為繼續遞歸下去的時候，正确答案，整個區間的第大已經不再是左兒子表示區間的第大了)。如此遞歸到葉子節點時即為答案。
- 整棵線段樹的根節點就表示整個值域有幾個數。
我們很容易看出：在權值線段樹中，采用元素到下标數組映射的方式進行插入。這樣會導緻一個問題：在資料離散程度較大的情況下，空間的利用效率比較低。是以我們對于線段樹所開空間不足時，常采用離散化的方式進行解決。
| 📕 | 此處的前導知識：離散化(具體的參見離散化的講解) |
2.權值線段樹的基本操作與實作
①.查詢第大/小元素
假設，那麼查詢過程是怎樣的？
首先我們從根節點出發，由于要查詢第大，是相對于終點而言的，是以從右子結點開始判斷：
目前節點右子樹包含個元素，是以應該向左子樹周遊，注意：此時應該減去右子樹的個元素！
尋找第小的操作與上方類似，差別在于相對于起點OR終點而言(周遊時對左右子樹的判斷順序)。
再次回顧整個步驟：對于整列數中第大/小的值，我們從根節點開始判斷（這裡按第大為例），如果比右兒子大，就說明第大的數在左子樹中。然後，要減去右子節點的值。（這是因為繼續遞歸下去的時候，正确答案，整個區間的第大已經不再是左子樹表示區間的第大了)。如此遞歸到葉子節點時即為答案
根據以上分析步驟，我們可以寫出查詢第大和第小的函數：
int query_kth(int pos, int l, int r, int k){
if(l == r) return l;
int mid = (l + r) >> 1, right = tree[pos << 1 | 1];
if(k <= right) return query(pos << 1 | 1, mid + 1, r, k);
else return query(pos << 1, l, mid, k - right);
} int query_kth(int pos, int l, int r, int k){
if(l == r) return l;
int mid = (l + r) >> 1, left = tree[pos << 1];
if(k <= left) return query(pos << 1, l, mid, k);
else return query(pos << 1 | 1, mid + 1, r, k - left);
} ②.單點更新操作
類似基礎線段樹，遞歸到葉子節點然後回溯
void add(int l, int r, int v, int x){
if (l == r) tree[v]++;
else{
int mid = (l + r) >> 1;
if (x <= mid) add(l, mid, v << 1, x);
else add(mid + 1, r, v << 1 | 1, x);
tree[v] = tree[v << 1] + tree[v << 1 | 1];
}
} ③.查詢某個數出現的個數
樹上二分查找的思想，代碼如下：
int find(int l, int r, int v, int x){
if (l == r) return tree[v];
else{
int mid = (l + r) >> 1;
if (x <= mid) return find(l, mid, v << 1, x);
else return find(mid + 1, r, v << 1 | 1, x);
}
} ④.查詢一段區間的數出現的次數
int find(int l, int r, int v, int x, int y){
if (l == x && r == y) return tree[v];
else{
int mid = (l + r) >> 1;
if (y <= mid) return find(l, mid, v << 1, x, y);
else if (x > mid) return find(mid + 1, r, v << 1 | 1, x, y);
else return find(l, mid, v << 1, x, mid) + find(mid + 1, r, v << 1 | 1, mid + 1, y);
}
} 3.區間離散化
int get_discretization(){
for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i]; //讀入資料
sort(b + 1, b + n + 1);
int len = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i){
int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
a[i] = pos;
} //離散化
}