---
# System prepended metadata

title: 持久化線段樹

---

# 持久化線段樹

可用來計算區間第$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);  //再加入新的元素
		}
	}
}
```