国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

?「學習筆記」可持久化線段樹?

2年前作者：yi_fan0305分類：Toy博客閱讀(19)違法舉報

這篇具有很好參考價值的文章主要介紹了?「學習筆記」可持久化線段樹?。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

可持久化數(shù)據(jù)結構 (Persistent data structure) 總是可以保留每一個歷史版本，并且支持操作的不可變特性 (immutable)。
主席樹全稱是可持久化權值線段樹，給定 \(n\) 個整數(shù)構成的序列 \(a\)，將對于指定的閉區(qū)間 \(\left[l, r\right]\) 查詢其區(qū)間內(nèi)的第 \(k\) 小值。

圖片來自 \(\texttt{OI-wiki}\)

可持久化線段樹

變量

#define mid ((l + r) >> 1)
int rot;
int rt[M];

struct node {
	int l, r, val;
} nod[M];

l, r: 左右孩子的指針；
val: 權值；
rot: 動態(tài)開點計數(shù)器；
rt: 不同版本的根節(jié)點的編號。

過程

?「學習筆記」可持久化線段樹?
每次修改操作修改的點的個數(shù)是一樣的。
（例如上圖，修改了 \(\left[1,8\right]\) 中對應權值為 \(1\) 的結點，紅色的點即為更改的點）
只更改了 \(O_{\log{n}}\) 個結點，形成一條鏈，也就是說每次更改的結點數(shù) \(=\) 樹的高度。
主席樹不能使用 \(x\times 2，x\times 2+1\) 來表示左右兒子，而是應該動態(tài)開點，并保存每個節(jié)點的左右兒子編號。
在記錄左右兒子的基礎上，保存插入每個數(shù)的時候的根節(jié)點就可以實現(xiàn)持久化。
現(xiàn)在還有個問題，如何求 \(\left[l,r\right]\) 區(qū)間 \(k\) 小值。
這里我們再聯(lián)系另外一個知識：前綴和。
這個小東西巧妙運用了區(qū)間減法的性質(zhì)，通過預處理從而達到 \(O_1\) 回答每個詢問。
我們可以發(fā)現(xiàn)，主席樹統(tǒng)計的信息也滿足這個性質(zhì)。
如果需要得到 \(\left[l,r\right]\) 的統(tǒng)計信息，只需要用 \(\left[1,r\right]\) 的信息減去 \(\left[1,l - 1\right]\) 的信息就行了。
關于空間問題，直接上個 \(2^5\times 10^5\)（即 n << 5，大多數(shù)題目中空間限制都較為寬松，因此一般不用擔心空間超限的問題）。

操作

  • 建樹

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		return u;
	}
	nod[u].l = build(l, mid);
	nod[u].r = build(mid + 1, r);
	return u;
}

  • 創(chuàng)建新節(jié)點

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	nod[rot].val = nod[u].val + 1;
	return rot;
}

修改時是在原來版本的基礎上進行修改，先設置它們一樣，由于插入了一個新的數(shù)，所以 nod[rot].val = nod[u].val + 1;。

  • 插入新節(jié)點

int add(int u, int l, int r, int pos) {
	u = newnod(u);
	if (l == r)	return u;
	if (pos <= mid) {
		nod[u].l = add(nod[u].l, l, mid, pos);
	}
	else {
		nod[u].r = add(nod[u].r, mid + 1, r, pos);
	}
	return u;
}

if (pos <= mid) {
	nod[u].l = add(nod[u].l, l, mid, pos);
}
else {
	nod[u].r = add(nod[u].r, mid + 1, r, pos);
}

修改時只會修改一條鏈，那也就意味著只會修改左孩子或右孩子中的一個，另一個保持不變。

  • 查詢第 \(k\) 大

int query(int l, int r, int lr, int rr, int k) {
	int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
	if (l == r)	return l;
	if (k <= x) {
		return query(l, mid, nod[lr].l, nod[rr].l, k);
	}
	else {
		return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
	}
}

int x = nod[nod[rr].l].val - nod[nod[lr].l].val;

這里利用了前綴和，求的是在 \(lr\) 到 \(rr\) 這個版本之間，左孩子的數(shù)量增加了多少，即 \(\left[lr, rr\right]\) 的前 \(x\) 小的元素。

if (k <= x) {
	return query(l, mid, nod[lr].l, nod[rr].l, k);
}
else {
	return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
}

如果 \(k < x\)，那么說明第 \(k\) 大的數(shù)在右孩子上，否則就在左子樹上。

可持久化數(shù)組

這個來源于洛谷的【模板】可持久化線段樹 1（可持久化數(shù)組），需要支持修改操作，但沒有了查詢第 \(k\) 大操作和插入操作。

變量

#define mid ((l + r) >> 1)
int rot;
int rt[M];

struct node {
	int ls, rs, val;
} nod[(N << 5) + 10];

操作

  • 創(chuàng)建新節(jié)點

inline int newnod(int u) { // 創(chuàng)建新節(jié)點
	++ rot;
	nod[rot] = nod[u];
	return rot;
}

  • 建樹

int build(int l, int r) { // 建樹
	int u = ++ rot;
	if (l == r) {
		scanf("%d", &nod[u].val);
		return u;
	}
	nod[u].ls = build(l, mid);
	nod[u].rs = build(mid + 1, r);
	return u;
}

  • 修改

int modify(int u, int l, int r, int pos, int c) { // 修改
	u = newnod(u);
	if (l == r) {
		nod[u].val = c;
	}
	else {
		if (pos <= mid) {
			nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
		}
		else {
			nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
		}
	}
	return u;
}

  • 查詢

int query(int u, int l, int r, int pos) { // 查詢
	if (l == r) {
		return nod[u].val;
	}
	else {
		if (pos <= mid) {
			return query(nod[u].ls, l, mid, pos);
		}
		else {
			return query(nod[u].rs, mid + 1, r, pos);
		}
	}
}

模板

namespace Persistent { // 可持久化數(shù)據(jù)結構
#define mid ((l + r) >> 1)
	
	const int N = 1e6 + 5;
	const int M = (N << 5) + 10;
	
	struct persistent_arr { // 可持久化數(shù)組
		int rot;
		int rt[M];
		
		struct node {
			int ls, rs, val;
		} nod[(N << 5) + 10];
		
		inline int newnod(int u) { // 創(chuàng)建新節(jié)點
			++ rot;
			nod[rot] = nod[u];
			return rot;
		}
		
		int build(int l, int r) { // 建樹
			int u = ++ rot;
			if (l == r) {
				scanf("%d", &nod[u].val);
				return u;
			}
			nod[u].ls = build(l, mid);
			nod[u].rs = build(mid + 1, r);
			return u;
		}
		
		int modify(int u, int l, int r, int pos, int c) { // 修改
			u = newnod(u);
			if (l == r) {
				nod[u].val = c;
			}
			else {
				if (pos <= mid) {
					nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
				}
				else {
					nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
				}
			}
			return u;
		}
		
		int query(int u, int l, int r, int pos) { // 查詢
			if (l == r) {
				return nod[u].val;
			}
			else {
				if (pos <= mid) {
					return query(nod[u].ls, l, mid, pos);
				}
				else {
					return query(nod[u].rs, mid + 1, r, pos);
				}
			}
		}
	};
	
	struct persistent_seg {
		int rot;
		int rt[M];
		
		struct node {
			int l, r, val;
		} nod[M];
		
		inline int newnod(int u) { // 創(chuàng)建新節(jié)點
			++ rot;
			nod[rot] = nod[u];
			nod[rot].val = nod[u].val + 1;
			return rot;
		}
		
		int build(int l, int r) { // 建樹
			int u = ++ rot;
			if (l == r) {
				return u;
			}
			nod[u].l = build(l, mid);
			nod[u].r = build(mid + 1, r);
			return u;
		}
		
		int add(int u, int l, int r, int pos) { // 插入新節(jié)點
			u = newnod(u);
			if (l == r)	return u;
			if (pos <= mid) {
				nod[u].l = add(nod[u].l, l, mid, pos);
			}
			else {
				nod[u].r = add(nod[u].r, mid + 1, r, pos);
			}
			return u;
		}
		
		int query(int l, int r, int lr, int rr, int k) { // 查找第 k 大的值
			int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
			if (l == r)	return l;
			if (k <= x) {
				return query(l, mid, nod[lr].l, nod[rr].l, k);
			}
			else {
				return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
			}
		}
	};
}

例題

【模板】可持久化線段樹 1（可持久化數(shù)組）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)

const int N = 1e6 + 5;

int n, m, rot;
int a[N], rt[N];

inline int read() {
	int x = 0;
	int fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

struct node {
	int ls, rs, val;
} nod[(N << 5) + 10];

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	return rot;
}

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		nod[u].val = a[l];
		return u;
	}
	nod[u].ls = build(l, mid);
	nod[u].rs = build(mid + 1, r);
	return u;
}

int modify(int u, int l, int r, int pos, int c) {
	u = newnod(u);
	if (l == r) {
		nod[u].val = c;
	}
	else {
		if (pos <= mid) {
			nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
		}
		else {
			nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
		}
	}
	return u;
}

int query(int u, int l, int r, int pos) {
	if (l == r) {
		return nod[u].val;
	}
	else {
		if (pos <= mid) {
			return query(nod[u].ls, l, mid, pos);
		}
		else {
			return query(nod[u].rs, mid + 1, r, pos);
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) {
		a[i] = read();
	}
	rt[0] = build(1, n);
	for (int i = 1, x, op, pos, val; i <= m; ++ i) {
		x = read(), op = read(), pos = read();
		if (op == 1) {
			val = read();
			rt[i] = modify(rt[x], 1, n, pos, val);
		}
		else {
			printf("%d\n", query(rt[x], 1, n, pos));
			rt[i] = rt[x];
		}
	}
}

【模板】可持久化線段樹 2文章來源地址http://www.zghlxwxcb.cn/news/detail-433970.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)

const int N = 1e6 + 5;
const int M = (N << 5) + 10;

int n, m;
int rot;
int a[N], tmp[N], rt[N];

struct node {
	int l, r, val;
} nod[M];

inline int getid(int c, int len) {
	return lower_bound(tmp + 1, tmp + len + 1, c) - tmp;
}

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	nod[rot].val = nod[u].val + 1;
	return rot;
}

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		return u;
	}
	nod[u].l = build(l, mid);
	nod[u].r = build(mid + 1, r);
	return u;
}

int add(int u, int l, int r, int pos) {
	u = newnod(u);
	if (l == r)	return u;
	if (pos <= mid) {
		nod[u].l = add(nod[u].l, l, mid, pos);
	}
	else {
		nod[u].r = add(nod[u].r, mid + 1, r, pos);
	}
	return u;
}

int query(int l, int r, int lr, int rr, int k) {
	int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
	if (l == r)	return l;
	if (k <= x) {
		return query(l, mid, nod[lr].l, nod[rr].l, k);
	}
	else {
		return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", a + i);
		tmp[i] = a[i];
	}
	sort(tmp + 1, tmp + n + 1);
	int len = unique(tmp + 1, tmp + n + 1) - tmp - 1;
	rt[0] = build(1, len);
	for (int i = 1; i <= n; ++ i) {
		rt[i] = add(rt[i - 1], 1, len, getid(a[i], len));
	}
	for (int i = 1, l, r, k; i <= m; ++ i) {
		scanf("%d%d%d", &l, &r, &k);
		printf("%d\n", tmp[query(1, len, rt[l - 1], rt[r], k)]);
	}
	return 0;
}

到了這里，關于?「學習筆記」可持久化線段樹?的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉載，請注明出處： 如若內(nèi)容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領支付寶紅包贊助服務器費用

相關文章

  • Unity學習筆記--數(shù)據(jù)持久化之PlayerPrefs的使用

    PlayerPrefs是Unity游戲引擎中的一個類，用于在游戲中存儲和訪問玩家的偏好設置和數(shù)據(jù)。它可以用來保存玩家的游戲進度、設置選項、最高分數(shù)等信息。PlayerPrefs將數(shù)據(jù)存儲在本地文件中，因此可以在游戲重新啟動時保持數(shù)據(jù)的持久性。 PlayerPrefs中存儲的數(shù)據(jù)存儲在哪里？ PC端

    2024年02月05日
    瀏覽(22)

  • 可持久化線段樹15（思維+亂搞）

    P4559 [JSOI2018]列隊 首先思考： 對于 [ l , r ] [l,r] [ l , r ] 區(qū)間內(nèi)的同學，他們集合之后與集合之前的相對大小是不會改變的，所有無論是否集合他們的相對的順序是不變的，那么集合到 [ k , k + r ? l ] [k,k+r-l] [ k , k + r ? l ] 的時候，他們的位置一定是固定的，我們可以將其稱之

    2024年02月09日
    瀏覽(19)
  • 微服務 - Redis緩存 · 數(shù)據(jù)結構 · 持久化 · 分布式 · 高并發(fā)

    微服務 - Redis緩存 · 數(shù)據(jù)結構 · 持久化 · 分布式 · 高并發(fā)

    系列目錄 微服務 - 概念 · 應用 · 架構 · 通訊 · 授權 · 跨域 · 限流 微服務 - Consul集群化 · 服務注冊 · 健康檢測 · 服務發(fā)現(xiàn) · 負載均衡 微服務 - Redis緩存 · 數(shù)據(jù)結構 · 持久化 · 分布式 · 高并發(fā) 微服務 - Nginx網(wǎng)關 · 進程機制 · 限流熔斷 · 性能優(yōu)化 · 動態(tài)負載 · 高可用

    2023年04月18日
    瀏覽(24)

  • Unity筆記：數(shù)據(jù)持久化的幾種方式

    主要方法： ScriptableObject PlayerPrefs JSON XML 數(shù)據(jù)庫（如Sqlite） PlayerPrefs 存儲的數(shù)據(jù)是 全局共享 的，它們存儲在用戶設備的本地存儲中，并且可以被應用程序的所有部分訪問。這意味著，無論在哪個場景、哪個腳本中，只要是同一個應用程序中的代碼，都可以讀取和修改 Playe

    2024年02月19日
    瀏覽(23)
  • 【Unity學習日記03】數(shù)據(jù)持久化

    【Unity學習日記03】數(shù)據(jù)持久化

    這一篇只能說寫了一部分，并沒有把Unity里數(shù)據(jù)持久化的操作講完整，之后可能是學到一點就記一點的模式。 數(shù)據(jù)持久化就是將內(nèi)存中的數(shù)據(jù)模型轉換為存儲模型，以及將存儲模型轉換為內(nèi)存中的數(shù)據(jù)模型的統(tǒng)稱。 人話版：將游戲數(shù)據(jù)存儲到硬盤，硬盤中數(shù)據(jù)讀取到游戲中，

    2024年02月12日
    瀏覽(17)
  • Spark大數(shù)據(jù)處理講課筆記--- RDD持久化機制

    Spark大數(shù)據(jù)處理講課筆記--- RDD持久化機制

    理解RDD持久化的必要性 了解RDD的存儲級別 學會如何查看RDD緩存 Spark中的RDD是懶加載的，只有當遇到行動算子時才會從頭計算所有RDD，而且當同一個RDD被多次使用時，每次都需要重新計算一遍，這樣會嚴重增加消耗。為了避免重復計算同一個RDD，可以將RDD進行持久化。 Spark中

    2024年02月06日
    瀏覽(30)

  • Spark大數(shù)據(jù)處理講課筆記3.5 RDD持久化機制

    2023年05月06日
    瀏覽(33)

  • Docker學習路線5：在 Docker 中實現(xiàn)數(shù)據(jù)持久化

    Docker 可以運行隔離的容器，包括應用程序和其依賴項，與主機操作系統(tǒng)分離。默認情況下，容器是臨時的，這意味著容器中存儲的任何數(shù)據(jù)在終止后都將丟失。為了解決這個問題并在容器生命周期內(nèi)保留數(shù)據(jù)，Docker 提供了各種數(shù)據(jù)持久化方法。 Docker 卷 綁定掛載 Docker tmpfs

    2024年02月16日
    瀏覽(23)
  • RabbitMQ學習筆記（消息發(fā)布確認，死信隊列，集群，交換機，持久化，生產(chǎn)者、消費者）

    RabbitMQ學習筆記（消息發(fā)布確認，死信隊列，集群，交換機，持久化，生產(chǎn)者、消費者）

    MQ（message queue）：本質(zhì)上是個隊列，遵循FIFO原則，隊列中存放的是message，是一種跨進程的通信機制，用于上下游傳遞消息。MQ提供“邏輯解耦+物理解耦”的消息通信服務。使用了MQ之后消息發(fā)送上游只需要依賴MQ，不需要依賴其它服務。 功能1：流量消峰 功能2：應用解耦 功

    2024年02月07日
    瀏覽(118)
  • PySpark大數(shù)據(jù)教程：深入學習SparkCore的RDD持久化和Checkpoint

    PySpark大數(shù)據(jù)教程：深入學習SparkCore的RDD持久化和Checkpoint

    本教程詳細介紹了PySpark中SparkCore的RDD持久化和Checkpoint功能，重點講解了緩存和檢查點的作用、如何進行緩存、如何設置檢查點目錄以及它們之間的區(qū)別。還提供了join操作的示例和Spark算子補充知識。

    2024年02月08日
    瀏覽(59)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

領取紅包

二維碼2

領紅包