首页 > 其他分享 >「学习笔记」FHQ-treap

「学习笔记」FHQ-treap

时间：2023-07-19 21:47:11浏览次数：47  
标签：Merge int t2 t3 笔记 t1 treap split FHQ

FHQ-treap，即无旋 treap，又称分裂合并 treap，支持维护序列，可持久化等特性。

FHQ-treap 有两个核心操作，分裂 与 合并。通过这两个操作，在很多情况下可以比旋转 treap 等方便的实现一些操作。

FHQ-treap 与其他的平衡树相比，他最明显的优点是：它好写！！！，想象一下，在考场上，你用较短的时间写出 FHQ-treap 和花很长时间敲 Splay，还得琢磨到底怎么旋转，优势就体现的很明显了，它和 treap 相比，它可以更好的进行区间操作，接下来将一一介绍。

平衡树也是一棵二叉搜索树。

结构体定义

定义

这里我们采取结构体来定义平衡树的节点，下面是最基本的节点信息。

struct node {
	int val, pai, siz;
	int ls, rs;
} t[N];

pai 是我们随机的一个值，val 是当前节点的权值，ls, rs 左右孩子，siz 是当前点的子树大小。

增加新节点

为了节省空间，我们一般会开一个“垃圾桶”来存储被删掉的节点的编号，要增加新节点时，如果垃圾桶里有节点，那么优先使用垃圾桶里的节点。回收利用很环保

vector<int> rub;
int newnod(int x) {
	int u;
	if (!rub.empty()) {
		u = rub.back();
		rub.pop_back();
	}
	else {
		u = ++ tot;
	}
	t[u].siz = 1;
	t[u].ls = t[u].rs = 0;
	t[u].val = x;
	t[u].pai = rand();
	return u;
}

分裂

分裂有两种，一种是按照节点个数来分裂，另一种是按照权值大小来分裂。

一般最常用的是按照节点个数分裂，但是按照权值大小分裂也会用到。

一般进行操作，我们的通用方法是将被操作点单独分裂成一棵树，对这棵树进行操作。

按照节点数量分裂的代码。

void split_rk(int u, int k, int &x, int &y) {
	if (u == 0) {
		x = y = 0;
		return ;
	}
	if (t[lc].siz + 1 <= k) {
		x = u;
		split_rk(rc, k - t[lc].siz - 1, t[u].rs, y);
	}
	else {
		y = u;
		split_rk(lc, k, x, t[u].ls);
	}
	pushup(u);
}

按照权值分裂的代码。

void split_val(int u, int v, int &x, int &y) { // x 和 y 是传参类型
	if (u == 0) {
		x = y = 0;
		return ;
	}
	if (t[u].val <= v) {
		x = u;
		split_val(rc, v, rc, y);
	}
	else {
		y = u;
		split_val(lc, v, x, lc);
	}
	pushup(u);
}

合并

在旋转 treap 中，我们借助旋转操作来维护堆的性质，同时旋转时还不能改变树的性质。在无旋 treap 中，我们用合并达到相同的效果。

因为两个 treap 已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。显然，根据堆的性质，我们需要把 \(pai\) 小的放在上面（这里采用小根堆）。

同时，我们还需要满足搜索树的性质。设 \(u < v\)，若 \(u\) 的 \(pai\) 小于 \(v\) 的，那么 \(u\) 即为新根结点，并且 \(v\) 因为值比 \(u\) 更大，应与 \(u\) 的右子树合并；反之，则 \(v\) 作为新根结点，然后因为 \(u\) 的值比 \(v\) 小，与 \(v\) 的左子树合并。

int Merge(int x, int y) {
	if (!x || !y) {
		return x + y;
	}
	if (t[x].pai < t[y].pai) {
		t[x].rs = Merge(t[x].rs, y);
		pushup(x);
		return x;
	}
	else {
		t[y].ls = Merge(x, t[y].ls);
		pushup(y);
		return y;
	}
}

基本操作

插入

将新节点要插入的位置分裂出来，然后合并即可。

void Insert(int x) {
	int u = newnod(x);
	int t1, t2;
	split_val(rt, x, t1, t2);
	rt = Merge(Merge(t1, u), t2);
}

删除

将要删除的节点分裂出来，将两边的子树合并即可。

void Erase(int x) {
	int t1, t2, t3;
	split_val(rt, x - 1, t1, t2);
	split_val(t2, x, t2, t3);
	rub.emplace_back(t2);
	t2 = Merge(t[t2].ls, t[t2].rs);
	rt = Merge(Merge(t1, t2), t3);
}

查找排名

将要查找的点按照权值分裂出来，前面分裂出去的树的大小 \(+ 1\) 就是排名。

int getrank(int x) {
	int t1, t2, rk;
	split_val(rt, x - 1, t1, t2);
	rk = t[t1].siz + 1;
	rt = Merge(t1, t2);
	ans ^= rk;
	las = rk;
	return rk;
}

查找排名为 \(x\) 的节点的权值

将要查找的点按照节点个数分裂出来，进行操作。

int getval(int x) {
	int t1, t2, t3, val;
	split_rk(rt, x - 1, t1, t2);
	split_rk(t2, 1, t2, t3);
	val = t[t2].val;
	ans ^= val;
	las = val;
	Merge(Merge(t1, t2), t3);
	return val;
}

查找前驱后继

利用分裂来查找。

int pre(int x) {
	int t1, t2, t3, pre;
	split_val(rt, x - 1, t1, t2);
	split_rk(t1, t[t1].siz - 1, t1, t3);
	pre = t[t3].val;
	rt = Merge(Merge(t1, t3), t2);
	ans ^= pre;
	las = pre;
	return pre;
}

int nxt(int x) {
	int t1, t2, t3, nxt;
	split_val(rt, x, t1, t2);
	split_rk(t2, 1, t2, t3);
	nxt = t[t2].val;
	rt = Merge(Merge(t1, t2), t3);
	ans ^= nxt;
	las = nxt;
	return nxt;
}

区间操作

P3391 【模板】文艺平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间翻转练习题

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc t[u].ls
#define rc t[u].rs

template<typename T>
inline T read() {
	T x = 0;
	bool 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;
}

const int N = 1e5 + 5;

int n, m, rt, tot;
vector<int> rub;

struct node {
	int val, tag;
	int ls, rs, siz, pai;
} t[N << 1];

inline void pushup(int u) {
	t[u].siz = t[lc].siz + t[rc].siz + 1;
}

inline void pushdown(int u) {
	if (!t[u].tag) {
		return ;
	}
	if (lc)	t[lc].tag ^= 1;
	if (rc)	t[rc].tag ^= 1;
	swap(t[u].ls, t[u].rs);
	t[u].tag = 0;
}

int newnod(int x) {
	int u = ++ tot;
	t[u].siz = 1;
	t[u].ls = t[u].rs = t[u].tag = 0;
	t[u].val = x;
	t[u].pai = rand();
	return u;
}

void split_rk(int u, int k, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return ;
	}
	pushdown(u);
	if (t[lc].siz + 1 <= k) {
		x = u;
		split_rk(rc, k - t[lc].siz - 1, rc, y);
	}
	else {
		y = u;
		split_rk(lc, k, x, lc);
	}
	pushup(u);
}

int Merge(int x, int y) {
	if (!x || !y) {
		return x + y;
	}
	if (t[x].pai < t[y].pai) {
		pushdown(x);
		t[x].rs = Merge(t[x].rs, y);
		pushup(x);
		return x;
	}
	else {
		pushdown(y);
		t[y].ls = Merge(x, t[y].ls);
		pushup(y);
		return y;
	}
}

void print(int u) {
	if (!u)	return ;
	pushdown(u);
	print(t[u].ls);
	printf("%d ", t[u].val);
	print(t[u].rs);
}

int main() {
	srand(time(NULL));
	n = read<int>(), m = read<int>();
	for (int i = 1; i <= n; ++ i) {
		rt = Merge(rt, newnod(i));
	}
	for (int i = 1, l, r; i <= m; ++ i) {
		l = read<int>(), r = read<int>();
		int t1, t2, t3;
		split_rk(rt, l - 1, t1, t2);
		split_rk(t2, r - l + 1, t2, t3);
		t[t2].tag ^= 1;
		rt = Merge(t1, Merge(t2, t3));
	}
	print(rt);
	return 0;
}

P2042 [NOI2005] 维护数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间操作的练习好题，涉及线段树操作。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc (t[u].ls)
#define rc (t[u].rs)

template<typename T>
inline T read() {
	T x = 0;
	bool 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;
}

const int N = 1e6 + 6;
mt19937 rnd(time(0));

int n, m, tot, rt;
int a[N];
vector<int> rub;

struct node {
	int pai, ls, rs, siz;
	ll val, sum, mx, maxpre, maxlas, tag;
	bool tag1, tag2;
} t[N];

int New(int x) {
	int u;
	if (!rub.empty()) {
		u = rub.back();
		rub.pop_back();
	} else {
		u = ++ tot;
	}
	t[u].sum = t[u].val = (t[u].mx = x);
	t[u].maxpre = t[u].maxlas = max(0, x);
	t[u].siz = 1;
	t[u].pai = rnd();
	t[u].tag1 = t[u].tag2 = (t[u].tag = 0);
	t[u].ls = t[u].rs = 0;
	return u;
}

void pushup(int u) {
	if (!u) return;
	t[u].siz = t[lc].siz + t[rc].siz + 1;
	t[u].sum = t[lc].sum + t[rc].sum + t[u].val;
	t[u].maxpre = max(max(t[lc].maxpre, t[lc].sum + t[u].val + t[rc].maxpre), 0ll);
	t[u].maxlas = max(max(t[rc].maxlas, t[rc].sum + t[u].val + t[lc].maxlas), 0ll);
	t[u].mx = max(0ll, t[lc].maxlas + t[rc].maxpre) + t[u].val;
	if (lc) t[u].mx = max(t[u].mx, t[lc].mx);
	if (rc) t[u].mx = max(t[u].mx, t[rc].mx);
}

void cover(int u, ll c) {
	t[u].val = t[u].tag = c;
	t[u].sum = t[u].siz * c;
	t[u].maxpre = t[u].maxlas = max(0ll, t[u].sum);
	t[u].mx = max(c, t[u].sum);
	t[u].tag1 = 1;
}

void Reverse(int u) {
	if (!u)	return ;
	swap(lc, rc);
	swap(t[u].maxpre, t[u].maxlas);
	t[u].tag2 ^= 1;
}

void pushdown(int u) {
	if (!u)	return ;
	if (t[u].tag2) {
		if (lc) {
			Reverse(lc);
		}
		if (rc) {
			Reverse(rc);
		}
		t[u].tag2 = 0;
	}
	if (t[u].tag1) {
		if (lc) {
			cover(lc, t[u].tag);
		}
		if (rc) {
			cover(rc, t[u].tag);
		}
		t[u].tag = t[u].tag1 = 0;
	}
}

void split(int u, int k, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return;
	}
	pushdown(u);
	if (t[lc].siz < k) {
		x = u;
		split(rc, k - t[lc].siz - 1, rc, y);
	} else {
		y = u;
		split(lc, k, x, lc);
	}
	pushup(u);
}

int Merge(int x, int y) {
	if (!x || !y) {
		return x + y;
	}
	if (t[x].pai < t[y].pai) {
		pushdown(x);
		t[x].rs = Merge(t[x].rs, y);
		pushup(x);
		return x;
	} else {
		pushdown(y);
		t[y].ls = Merge(x, t[y].ls);
		pushup(y);
		return y;
	}
}

int add(int l, int r) {
	if (l != r) {
		int mid = (l + r) >> 1;
		return Merge(add(l, mid), add(mid + 1, r));
	}
	return New(a[l]);
}

void Erase(int u) {
	if (!u)	return ;
	rub.emplace_back(u);
	if (lc) {
		Erase(lc);
	}
	if (rc) {
		Erase(rc);
	}
}

void print(int u) {
	if (!u)	return ;
	pushdown(u);
	print(lc);
	print(rc);
}

int main() {
	n = read<int>(), m = read<int>();
	for (int i = 1; i <= n; ++ i) {
		a[i] = read<int>();
	}
	rt = Merge(rt, add(1, n));
	string op;
	for (int i = 1, t1, t2, t3; i <= m; ++ i) {
		cin >> op;
		if (op == "INSERT") {
			int pos = read<int>(), len = read<int>();
			split(rt, pos, t1, t2);
			for (int i = 1; i <= len; ++ i) {
				a[i] = read<int>();
			}
			rt = Merge(Merge(t1, add(1, len)), t2);
		}
		if (op == "DELETE") {
			int pos = read<int>(), len = read<int>();
			split(rt, pos - 1, t1, t2);
			split(t2, len, t2, t3);
			Erase(t2);
			rt = Merge(t1, t3);
		}
		if (op == "MAKE-SAME") {
			int pos = read<int>(), len = read<int>(), v = read<int>();
			split(rt, pos - 1, t1, t2);
			split(t2, len, t2, t3);
			cover(t2, v);
			rt = Merge(Merge(t1, t2), t3);
		}
		if (op == "REVERSE") {
			int pos = read<int>(), len = read<int>();
			split(rt, pos - 1, t1, t2);
			split(t2, len, t2, t3);
			Reverse(t2);
			rt = Merge(Merge(t1, t2), t3);
		}
		if (op == "GET-SUM") {
			int pos = read<int>(), len = read<int>();
			split(rt, pos - 1, t1, t2);
			split(t2, len, t2, t3);
			printf("%lld\n", t[t2].sum);
			rt = Merge(Merge(t1, t2), t3);
		}
		if (op == "MAX-SUM") {
			printf("%lld\n", t[rt].mx);
		}
	}
	return 0;
}

P2596 [ZJOI2006] 书架 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

模板题

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc t[u].ls
#define rc t[u].rs

template<typename T>
inline T read() {
	T x = 0;
	bool 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;
}

const int N = 8e4 + 5;

mt19937 rnd(time(0));

int n, m, tot, rt;
int Id[N];

struct node {
	int val, siz, pai;
	int ls, rs, fa;
} t[N << 1];

void pushup(int u) {
	t[u].siz = t[lc].siz + t[rc].siz + 1;
	t[lc].fa = t[rc].fa = u;
}

int New(int x) {
	int u = ++ tot;
	t[u].siz = 1;
	t[u].val = x;
	t[u].pai = rnd();
	t[u].ls = t[u].rs = t[u].fa = 0;
	Id[x] = u;
	return u;
}

int Find(int u) {
	int res = t[t[u].ls].siz + 1;
	for (; u != rt; u = t[u].fa) {
		if (t[t[u].fa].rs == u) {
			res += t[t[t[u].fa].ls].siz + 1;
		}
	}
	return res;
}

void split_rk(int u, int k, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return ;
	}
	if (t[lc].siz < k) {
		x = u;
		split_rk(rc, k - t[lc].siz - 1, rc, y);
	} else {
		y = u;
		split_rk(lc, k, x, lc);
	}
	pushup(u);
}

int Merge(int x, int y) {
	if (!x || !y) {
		return x + y;
	}
	if (t[x].pai < t[y].pai) {
		t[x].rs = Merge(t[x].rs, y);
		pushup(x);
		return x;
	} else {
		t[y].ls = Merge(x, t[y].ls);
		pushup(y);
		return y;
	}
}

int main() {
	n = read<int>(), m = read<int>();
	for (int i = 1; i <= n; ++ i) {
		rt = Merge(rt, New(read<int>()));
	}
	for (int i = 1, x, t1, t2, t3, t4; i <= m; ++ i) {
		string op;
		cin >> op;
		x = read<int>();
		if (op == "Top") {
			int k = Find(Id[x]);
			split_rk(rt, k - 1, t1, t2);
			split_rk(t2, 1, t2, t3);
			rt = Merge(Merge(t2, t1), t3);
		}
		if (op == "Bottom") {
			int k = Find(Id[x]);
			split_rk(rt, k - 1, t1, t2);
			split_rk(t2, 1, t2, t3);
			rt = Merge(Merge(t1, t3), t2);
		}
		if (op == "Insert") {
			int y = read<int>();
			int k = Find(Id[x]);
			if (y > 0) {
				split_rk(rt, k - 1, t1, t2);
				split_rk(t2, 1, t2, t3);
				split_rk(t3, y, t3, t4);
				rt = Merge(Merge(t1, t3), Merge(t2, t4));
			} else {
				split_rk(rt, k - 1, t1, t2);
				split_rk(t2, 1, t2, t3);
				split_rk(t1, k + y - 1, t1, t4);
				rt = Merge(Merge(t1, t2), Merge(t4, t3));
			}
		}
		if (op == "Ask") {
			cout << Find(Id[x]) - 1 << '\n';
		}
		if (op == "Query") {
			split_rk(rt, x - 1, t1, t2);
			split_rk(t2, 1, t2, t3);
			cout << t[t2].val << '\n';
			rt = Merge(Merge(t1, t2), t3);
		}
	}
	return 0;
}

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc t[u].ls
#define rc t[u].rs

template<typename T>
inline T read() {
	T x = 0;
	bool 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;
}

const int N = 2e5 + 5;

int n, tot, top, rt;
vector<int> rub;

struct node {
	int val, pai, siz;
	int ls, rs;
} t[N];

inline int newnod(int x) {
	int u;
	if (!rub.empty()) {
		u = rub.back();
		rub.pop_back();
	}
	else {
		u = ++ tot;
	}
	t[u].siz = 1;
	t[u].ls = t[u].rs = 0;
	t[u].val = x;
	t[u].pai = rand();
	return u;
}

inline void pushup(int u) {
	t[u].siz = t[lc].siz + 1 + t[rc].siz;
}

void split_rk(int u, int k, int &x, int &y) {
	if (u == 0) {
		x = y = 0;
		return ;
	}
	if (t[lc].siz + 1 <= k) {
		x = u;
		split_rk(rc, k - t[lc].siz - 1, t[u].rs, y);
	}
	else {
		y = u;
		split_rk(lc, k, x, t[u].ls);
	}
	pushup(u);
}

void split_val(int u, int v, int &x, int &y) {
	if (u == 0) {
		x = y = 0;
		return ;
	}
	if (t[u].val <= v) {
		x = u;
		split_val(rc, v, rc, y);
	}
	else {
		y = u;
		split_val(lc, v, x, lc);
	}
	pushup(u);
}

int Merge(int x, int y) {
	if (!x || !y) {
		return x + y;
	}
	if (t[x].pai < t[y].pai) {
		t[x].rs = Merge(t[x].rs, y);
		pushup(x);
		return x;
	}
	else {
		t[y].ls = Merge(x, t[y].ls);
		pushup(y);
		return y;
	}
}

inline void Insert(int x) {
	int u = newnod(x);
	int t1, t2;
	split_val(rt, x, t1, t2);
	rt = Merge(Merge(t1, u), t2);
}

inline void Erase(int x) {
	int t1, t2, t3;
	split_val(rt, x - 1, t1, t2);
	split_val(t2, x, t2, t3);
	rub.emplace_back(t2);
	t2 = Merge(t[t2].ls, t[t2].rs);
	rt = Merge(Merge(t1, t2), t3);
}

inline int getrank(int x) {
	int t1, t2, rk;
	split_val(rt, x - 1, t1, t2);
	rk = t[t1].siz + 1;
	rt = Merge(t1, t2);
	return rk;
}

inline int getval(int x) {
	int t1, t2, t3, val;
	split_rk(rt, x - 1, t1, t2);
	split_rk(t2, 1, t2, t3);
	val = t[t2].val;
	Merge(Merge(t1, t2), t3);
	return val;
}

inline int pre(int x) {
	int t1, t2, t3, pre;
	split_val(rt, x - 1, t1, t2);
	split_rk(t1, t[t1].siz - 1, t1, t3);
	pre = t[t3].val;
	rt = Merge(Merge(t1, t3), t2);
	return pre;
}

inline int las(int x) {
	int t1, t2, t3, las;
	split_val(rt, x, t1, t2);
	split_rk(t2, 1, t2, t3);
	las = t[t2].val;
	rt = Merge(Merge(t1, t2), t3);
	return las;
}

int main() {
	n = read<int>();
	for (int i = 1, x, op; i <= n; ++ i) {
		op = read<int>(), x = read<int>();
		switch(op) {
		case 1 :
			Insert(x);
			break ;
		case 2 :
			Erase(x);
			break ;
		case 3 :
			printf("%d\n", getrank(x));
			break ;
		case 4 :
			printf("%d\n", getval(x));
			break ;
		case 5 :
			printf("%d\n", pre(x));
			break ;
		case 6 :
			printf("%d\n", las(x));
			break ;
		}
	}
	return 0;
}

标签：Merge,int,t2,t3,笔记,t1,treap,split,FHQ
From： https://www.cnblogs.com/yifan0305/p/17566837.html

相关文章

  • python笔记：第十一章正则表达式
    1.模块re以一定规则，快速检索文本，或是实现一些替换操作默认下，区分大小写2.常见的匹配字符表字符描述\d代表任意数字，就是阿拉伯数字0-9这些\D代表非数字的字符。与\d完全相反\w代表字母，数字，下划线。也就是a-z、A-Z、0-9、_\W跟\w相反，代表不是字母......
  • StarRocks Segment源码阅读笔记--Page的组成
    Page由4部分组成PageBody，PageFooter，FooterSize(4)，CheckSum(4)PageBody是由page类型决定的，可能是压缩的。PageFooter是经过序列化的PageFooterPB。它包含page_type、未压缩的body大小和其他通用的元数据。如果PageBody的大小和未压缩的body大小一致，则表示这个page是未压缩的。F......
  • 特征平台笔记
    AI从2012年开始快速发展，在人脸识别、广告、个性化推荐等领域大规模商用后，陆续出现了一些通用的平台来加速模型训练和模型部署流程，例如：AWSSageMaker ：通过完全托管的基础设施、工具和工作流程为任何用例构建、训练和部署机器学习(ML)模型Google VertexAI ：使用全代管式机......
  • XOps笔记
     当前是 Ops盛行的时代，在互联网圈内的你一定经常都会听到这些名词，DevOps、DevSecOps、GitOps、NetOps、ItOps、Aiops、DataOps、MLOps、NoOps；无论是什么Ops，它的目标都是利用DevOps的最佳实践去实现效率和规模经济，并确保可靠性、可重用性和可重复性，同时减少技术和流程的重复，从......
  • 主席树学习笔记
    Tip：建议完成LuoguP3919后阅读。目录模板：静态区间\(k\)小值模板：动态区间\(k\)小值BZOJ3207：花神的嘲讽计划疯狂的颜色序列SPOJ10628：CountonatreeLuoguP3302森林模板题：静态区间\(k\)小值思路引导首先我们想一想，如何用线段树求数列\(k\)小值。我们可以建......
  • 白话机器学习笔记（二）学习分类
    分类用图形来解释，把他想象为有大小有方向带箭头的向量。设权重向量为\(w\)，虚线为使权重向量称为法线向量的直线。直线的表达式为：\(w\cdotx=0\)(两个向量的内积)也可写为：\(w\cdotx=\sum\limits_{i=1}^nw_ix_i=w_1x_1+w_2x_2=0\)\(w\cdotx=|w|\cdot|x|\cdotcos\theta\)要......
  • 白话机器学习笔记（一）学习回归
    最小二乘法定义模型表达式：\(f_\theta(x)=\theta_0+\theta_1x\)（常用\(\theta\)表示未知数、\(f_\theta(x)\)表示含有参数\(\theta\)并且和变量\(x\)相关的函数）目标函数假设有\(n\)个训练数据，那么它们的误差之和可以这样表示，这个表达式称为目标函数。\(E(\theta)=\frac12\sum......
  • 白话机器学习笔记（三）评估模型
    模型评估在进行回归和分类时，为了进行预测，我们定义了函数\(f_\theta(x)\)，然后根据训练数据求出了函数的参数\(\theta\)。如何预测函数\(f_\theta(x)\)的精度？看它能否很好的拟合训练数据？我们需要能够定量的表示机器学习模型的精度，这就是模型的评估。交叉验证回归问题的验证把......
  • KMP算法笔记
    1.概念解析前置：将原串称之为文本串，匹配串称之为模式串。KMP的实质其实就是：利用已经匹配的信息，来加速查找的过程。对于暴力解法而言，当我进行模式串匹配时，遇到一个不匹配的字符，那么只能一步一步往下滑动，然后重新匹配。但是对于KMP算法而言，利用到了前缀子......
  • Web前端学习笔记
    <!DOCTYPEhtml><htmllang="en"><head>  <metacharset="UTF-8">  <metaname="viewport"content="width=device-width,initial-scale=1.0">  <title>welcometomyworld</ti......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99