# 持久化線段樹
可用來計算區間第$K$小的數
## 無更改
### substack 1
題目 : 求整個數列的第$K$小
#### Solution 1
排序
#### Solution 2:
**開1顆線段樹，依序把$a_i$是第$k$小的$k$加進去線段樹中，並紀錄區間個數**
在查詢的時候，如果當前查詢的$K$小於等於$L\_num$(左子樹的值:第$l$小元素值到第$m$小元素值的個數總和)，代表第$K$小在左子樹中，則遞迴左子樹$(l,mid,K)$，否則遞迴右子樹$(mid+1,r,K-L\_num)$，因為$L\_num$個元素已經在在左子樹了，所以在查詢右子樹的時候必須減掉$L\_num$，用於查詢區間$[mid+1,r]$的第$K-L\_num$小。
```cpp=
int query(int node,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)/2,L_num=tree[node*2+1];
if(k<=L_num) return query(node*2+1,l,mid,k);
else return query(node*2+2,mid+1,r,k-L_num);
}
```
### substack 2
引用前綴和概念，當要求區間$[l,r]$的時候可以用。
```
ans=pre[R]-pre[L-1]
```
**合併以上兩個想法**
因為要多了一個區間的條件，所以在計算$L\_num$時就要利用到subtask 2，可以建立$n$顆線段樹，每一顆線段樹紀錄前綴的資訊(也就是$1$到當前元素)，樹中存放前綴的每個元素為第幾小的資訊，接著用subtask 1的方法遞迴，在計算$L\_num$時要用第$R$顆線段樹左子樹的值$-$第$L-1$顆線段樹左子樹的值來判斷區間左子樹的值。
#### 優化
但這樣會MLE，觀察一下，第$i$顆樹的更新只會跟左子樹或右子樹其中一個有關(看當前的第$K$小在左邊或右邊)，另一邊不會動到，跟第$i-1$顆樹是一樣的，所以可共用節點，實作上就是先建立一個節點，然後初始為跟第$i-1$顆樹的同一個節點一樣，再看更新的值在左子樹或右子樹，直接覆蓋就好了。
```cpp=
int update(int pre,int l,int r,int Kth){
int root=node++;
//初始化為跟pre節點一樣,連到pre節點與之共用
L[root]=L[pre];
R[root]=R[pre];
//sum為pre的sum加現在更新的pos
sum[root]=sum[pre]+1;
if(l==r) return root;
int mid=(l+r)/2;
if(Kth<=mid) L[root]=update(L[pre],l,mid,Kth);
//如果第Kth小的元素比mid還小,代表要更新左子樹,右子樹與原來的共用
else R[root]=update(R[pre],mid+1,r,Kth);
//如果第Kth小的元素比mid還大,代表要更新右子樹,左子樹與原來的共用
return root;
}
```
#### 查詢
基本上跟subtask 1一樣，差別只在於左子樹的計算要用$(segtree[R]'s\ L\_num)-(segtree[L-1]'s\ L\_num)$，也就是區間$[1,R]$小於等於第$m$大的元素個數總和減掉區間$[1,L-1]$小於等於第$m$大的元素個數總和，這樣就會是區間$[L,R]$小於等於第$m$大的元素個數總和$L\_num$。
```cpp=
int query(int u,int v,int l,int r,int k){
if(l==r) return l;
int m=(l+r)/2;
int L_num=sum[L[v]]-sum[L[u]]; //計算區間[l,r]中左子樹的元素個數
if(k<=L_num) return query(L[u],L[v],l,m,k);
//如果左子樹的數量<=k代表第k大的元素在左半邊
else return query(R[u],R[v],m+1,r,k-L_num);
//否則在右半邊,要更新成查詢區間[m+1,r]第k-L_num大的元素
}
```
#### 完整Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
//-----------------------------------
int a[MAXN],Hash[MAXN],node=1;
int sum[MAXN<<5]; //sum[i]為前i小元素的數量
int L[MAXN<<5]; //L[i]為i的左孩子的節點編號
int R[MAXN<<5]; //R[i]為i的右孩子的節點編號
int Root[MAXN]; //Root[i]為第i個元素的線段樹的Root
int built(int l,int r){ //返回自己節點編號
int root=node++;
if(l==r) return root;
int mid=(l+r)/2;
L[root]=built(l,mid);
R[root]=built(mid+1,r);
return root;
}
int update(int pre,int l,int r,int Kth){
int root=node++;
//初始化為跟pre節點一樣,連到pre節點與之共用
L[root]=L[pre];
R[root]=R[pre];
//sum為pre的sum加現在更新的pos
sum[root]=sum[pre]+1;
if(l==r) return root;
int mid=(l+r)/2;
if(Kth<=mid) L[root]=update(L[pre],l,mid,Kth);
//如果第Kth小的元素比mid還小,代表要更新左子樹,右子樹與原來的共用
else R[root]=update(R[pre],mid+1,r,Kth);
//如果第Kth小的元素比mid還大,代表要更新右子樹,左子樹與原來的共用
return root;
}
int query(int u,int v,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)/2;
int L_num=sum[L[v]]-sum[L[u]]; //計算區間[l,r]中左子樹的元素個數
if(k<=L_num) return query(L[u],L[v],l,mid,k);
//如果左子樹的數量<=k代表第k大的元素在左半邊
else return query(R[u],R[v],mid+1,r,k-L_num);
//否則在右半邊,要更新成查詢區間[mid+1,r]第k-L_num大的元素
}
void solve(){
int n,q;
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> a[i];
Hash[i]=a[i];
}
//離算化+去除重複元素,此後為區間為[1,m]
sort(Hash+1,Hash+n+1);
int m=unique(Hash+1,Hash+n+1)-(Hash+1);
node=1;
Root[0]=built(1,m); //類似前綴和概念:pre[0]=0,Root[0]=空樹
for(int i=1;i<=n;i++){
int Kth=lower_bound(Hash+1,Hash+m+1,a[i])-Hash; //求元素a[i]為第幾小
Root[i]=update(Root[i-1],1,m,Kth); //更新元素a[i]的線段樹
}
while(q--){
int l,r,k;
cin >> l >> r >> k;
int Kth=query(Root[l-1],Root[r],1,m,k); //查詢線段樹(Root[r]-Root[l-1])
cout << Hash[Kth] << '\n'; //對應回元素a[i]
}
}
signed main(){
cin.sync_with_stdio(0),cin.tie(0);
int t;
cin >> t;
while(t--) solve();
}
```
## 有更新
主要建樹和上面都是大同小異,只差在有更新要用到BIT,因為如果用前綴和的概念去建樹,每次更新會影響到後面的每一棵樹,但是用BIT就不用每個節點都更新到了,時間複雜度大大減小
其概念就是每個BIT節點都是一棵線段樹,在更新和查詢時,都在BIT會跑的節點執行
### 更新
在更新的時候,要更新的樹的根結點不再是由上面的單一節點,而是bit遍歷到的節點,每個節點都要更新
為了持久化,也就是後面的樹的節點如果跟前面的樹的節點一樣,可以共用,所以前面的節點不能被覆蓋或刪掉,這時候我們只要更新新樹的根結點就好了,並不會覆蓋掉前面的節點,因為節點編號是會一直遞增下去的
```cpp=
int update(int pre,int l,int r,int Kth,int change){
int now=++cnt;
L[now]=L[pre];
R[now]=R[pre];
number[now]=number[pre]+change;
if(l==r) return now;
int mid=(l+r)>>1;
if(Kth<=mid) L[now]=update(L[pre],l,mid,Kth,change);
else R[now]=update(R[pre],mid+1,r,Kth,change);
return now;
}
void add(int x,int change){ //bit
int Kth=lower_bound(all(disc),a[x])-disc.begin()+1; //求第x個元素為第K大
while(x<m){ //m為bit大小
root[x]=update(root[x],1,m,Kth,change); //把更新後的樹的根結點放到root[x]
x+=x&-x;
}
}
```
### 查詢
查詢的時候不再是上面的sum[L[v]]-sum[L[u]],而是BIT節點的相加,就跟一般查詢前綴和的作法是一樣的
#### 預處理
首先我們需要先建立一個所有BIT會跑到的節點編號,有左邊界和右邊界,所以要建立兩個,接下來的查詢都在這些節點上
```cpp=
vector<int> v[2]; //0:左邊界 1:右邊界
void init(int x,int i){
while(x){
v[i].pb(root[x]); //紀錄BIT遍歷到的樹的根結點
x-=x&-x;
}
}
```
#### 查詢
在查詢的時候就把這些節點的值相加,就跟BIT計算前綴和的作法是一樣的
```cpp=
int query(int l,int r,int Kth){
if(l==r) return l;
//計算左子樹的數量
int L_num=0;
for(auto i:v[1]) L_num+=number[L[i]]; //右邊界的BIT
for(auto i:v[0]) L_num-=number[L[i]]; //左邊界的BIT
int mid=(l+r)>>1;
if(Kth<=L_num){ //第K小在左邊,往左走
//更新每棵樹的根結點=>此節點的左節點
for(auto &i:v[0]) i=L[i];
for(auto &i:v[1]) i=L[i];
return query(l,mid,Kth);
}else{ //第K小在右邊,往右走
//更新每棵樹的根結點=>此節點的右節點
for(auto &i:v[0]) i=R[i];
for(auto &i:v[1]) i=R[i];
return query(mid+1,r,Kth-L_num);
}
}
```
### 完整Code
```cpp=
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define binary_search
#define inf LLONG_MAX
#define mod 1000000007
#define MAXN 32005
int N=1,n,m,x,k,ans;
//-----------------------------------
struct Que{
char info;
int l,r,i,w,k;
}que[5005];
int a[MAXN],root[MAXN*2],L[MAXN*400],R[MAXN*400],number[MAXN*400],cnt;
vector<int> disc; //Discretization
//---------------update-----------------
int update(int pre,int l,int r,int Kth,int change){
int now=++cnt;
L[now]=L[pre];
R[now]=R[pre];
number[now]=number[pre]+change;
if(l==r) return now;
int mid=(l+r)>>1;
if(Kth<=mid) L[now]=update(L[pre],l,mid,Kth,change);
else R[now]=update(R[pre],mid+1,r,Kth,change);
return now;
}
void add(int x,int change){
int Kth=lower_bound(all(disc),a[x])-disc.begin()+1;
while(x<m){
root[x]=update(root[x],1,m,Kth,change); //把更新後的樹的根結點放到root[x],為
x+=x&-x;
}
}
//--------------update-----------------
//--------------query------------------
vector<int> v[2];
void init(int x,int i){
while(x){
v[i].pb(root[x]);
x-=x&-x;
}
}
int query(int l,int r,int Kth){
if(l==r) return l;
int L_num=0;
for(auto i:v[1]) L_num+=number[L[i]]; //右邊界
for(auto i:v[0]) L_num-=number[L[i]]; //左邊界
int mid=(l+r)>>1;
if(Kth<=L_num){
for(auto &i:v[0]) i=L[i];
for(auto &i:v[1]) i=L[i];
return query(l,mid,Kth);
}else{
for(auto &i:v[0]) i=R[i];
for(auto &i:v[1]) i=R[i];
return query(mid+1,r,Kth-L_num);
}
}
//--------------query------------------
signed main(){
cin.sync_with_stdio(0),cin.tie(0);
int q;
//-------input-----------
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> a[i];
disc.pb(a[i]); //加入離散化的陣列
}
for(int i=1;i<=q;i++){
cin >> que[i].info;
if(que[i].info=='C'){ //更新
cin >> que[i].i >> que[i].w;
disc.pb(que[i].w); //加入離散化的陣列
}else{ //查詢
cin >> que[i].l >> que[i].r >> que[i].k;
}
}
//------------------------
//-----離散化------
sort(all(disc));
m=unique(all(disc))-disc.begin()+1;
//----------------
//------建樹-------
for(int i=1;i<=n;i++) add(i,1);
//-----------更新和查詢------------
for(int i=1;i<=q;i++){
if(que[i].info=='Q'){ //查詢
v[0].clear(),v[1].clear();
//初始化bit會用到的bit編號
init(que[i].l-1,0);
init(que[i].r,1);
cout << disc[query(1,m,que[i].k)-1] << '\n';
}else{ //更新
add(que[i].i,-1); //先把之前的元素刪掉
a[que[i].i]=que[i].w;
add(que[i].i,1); //再加入新的元素
}
}
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
