首页 > 其他分享 >树状数组及线段树详解

树状数组及线段树详解

时间：2024-02-19 09:11:22浏览次数：33  
标签：树状 int 线段 tr long 详解 ls sum id

本文章是作者调了3个多小时后，感触颇深，历经1个多小时写出来的，不喜勿喷

相关内容可参考 模板总结 中的树状数组及线段树；

进入正题

树状数组

所谓树状数组，即像树的数组，一般应用于求多次前缀和以及区间前缀和的问题中；

其根据节点编号的二进制数的末尾0的个数划分层次，每个节点的管辖范围为2^k，其中k为此节点的二进制数末尾0的个数，并用lowbit实现跳父亲的操作；

所谓lowbit，就是一个数的二进制的从右往左数第一个1出现的位置和这个1右面所有0构成的数，如6 == 110, 则lowbit(6) == 10 == 2; 6 + lowbit(6) == 8 == 1000，则节点8是节点6的父亲（父亲由其儿子数值加和转移而来，具体见下图）；

image

树状数组的主要题目有三类：

1.单点修改，区间查询（树状数组操作的基础，后面的2个操作都是由它转变而来）；

对于单点修改，我们只需先修改它自己，然后一步步修改其父亲即可；

对于区间查询，根据上面的思路，我们可以知道，树状数组可以查询1i的区间和，如果要查询xy的区间和，只需用（1 ~ y） - （1 ~ x - 1）即可；

模板题

点击查看代码 
#include <iostream>
#include <string>
using namespace std;
int n, m;
int a[1000005];
int t[1000005];
string s;
int lowbit(int x) {
	return x & (-x);
}
void add_dian(int x, int k) { //对第x个数加k（单点修改）；
	while(x <= n) {
		t[x] += k;
		x += lowbit(x);
	}
}
int ask_he(int l, int r) { //查询区间和（区间查询）；
	int ans = 0;
	int i = l - 1;
	while(i > 0) {
		ans -= t[i];
		i -= lowbit(i);
	}
	i = r;
	while(i > 0) {
		ans += t[i];
		i -= lowbit(i);
	}
	return ans;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		add_dian(i, a[i]);
	}
	cin >> m;
	int c, d;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		cin >> c >> d;
		if (s == "ADD") {
			add_dian(c, d);
		}
		if (s == "SUM") {
			cout << ask_he(c, d) << endl;
		}
	}
	return 0;
}

2.区间修改，单点查询；

对于区间修改，我们如果遍历修改的话会TLE，所以我们要维护原数组的差分数组b，每次修改区间(x, y)时只需修改x 和 y + 1的值即可（将b[x] + k, b[y + 1] - k）；

对于单点查询i，我们只需求b的前缀和(1 ~ i）即可；

记得开long long!

模板题

点击查看代码 
#include <iostream>
#include <string>
using namespace std;
int n, m;
string s;
int a[1000005];
int b[1000005]; //a的差分数组；
int t[1000005]; //维护b的树状数组；
int lowbit(int x) {
	return x & (-x);
}
void add_dian(int x, int k) {
	while(x <= n) {
		t[x] += k;
		x += lowbit(x);
	}
}
//如要进行区间修改，只需将起点加k，终点 + 1减k（差分数组）；
long long ask_dian(int x) { //输出点（a数组中，x为位置）；
	long long ans = 0;
	while(x > 0) {
		ans += t[x];
		x -= lowbit(x);
	}
	return ans;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] - a[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		add_dian(i, b[i]);
	}
	cin >> m;
	int c, d, e;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		if (s == "ADD") {
			cin >> c >> d >> e;
			add_dian(c, e);
			add_dian(d + 1, -e);
		}
		if (s == "QUERY") {
			cin >> c;
			cout << ask_dian(c) << endl;
		}
	}
	return 0;
}

3.区间修改，区间查询；
这个比较麻烦，需要推公式，个人感觉最好用线段树做；

公式的推导：

设T(n) 为原数组的前缀和，S(n)为差分数组的前缀和；

则：

\[T(n) == S(1) + S(2) + ... + S(n) \]

\[== b1 + (b1 + b2) + (b1 + b2 + b3) + ... + (b1 + b2 + ... + bn) \]

\[== nb1 + (n - 1)b2 + ... + bn \]

\[== (n + 1)(b1 + b2 + ... + bn) - (b1 + 2b2 + 3b3 + ... + nbn) \]

\[== (n + 1)\sum^{i}_{i <= n} bi - \sum^i_{i <= n} i * bi \]

所以，我们只需维护两个树状数组（差分数组的和i*差分数组的）即可；

模板题

点击查看代码 
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int n, m;
string s;
int a[100005];
int b[100005]; //a的差分数组；
long long t[100005]; //维护b的树状数组；
long long t1[100005]; //
int lowbit(int x) {
	return x & (-x);
}
void add_dian(int x, long long k) {
	long long val = 1ll * k * x; //(x + a[i]) * y 和 a[i] * y 差 x * y；
	while(x <= n) {
		t[x] += k;
		t1[x] += val;
		x += lowbit(x);
	}
}
void add_dian1(int x, long long k) {
	while(x <= n) {
		t1[x] += k;
		x += lowbit(x);
	}
}
//如要进行区间修改，只需将起点加k，终点减k（差分数组）；
long long ask_sum(int x) {
	long long ans = 0;
	while(x > 0) {
		ans += t[x];
		x -= lowbit(x);
	}
	return ans;
}
long long ask_sum1(int x) {
	long long ans = 0;
	while(x > 0) {
		ans += t1[x];
		x -= lowbit(x);
	}
	return ans;
}
long long ask(int l, int r) {
	long long ans1 = ask_sum(r) * (r + 1) - ask_sum(l - 1) * l; //根据公式(x + 1) * ask_sum(x) - ask_sum1(x)得来（只不过前面的x + 1分开了）（以前是r 和 l - 1，因为公式(x + 1)，所以是(r + 1) 和 l；
	long long ans2 = ask_sum1(r) - ask_sum1(l - 1);
	return ans1 - ans2;
}
int main() {
	memset(t, 0, sizeof(t));
	memset(t1, 0, sizeof(t1));
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] - a[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		add_dian(i, b[i]);
	}
	cin >> m;
	int c, d;
	long long e;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		if (s == "ADD") {
			cin >> c >> d >> e;
			add_dian(c, e);
			add_dian(d + 1, -e);
		}
		else {
			cin >> c >> d;
			cout << ask(c, d) << endl;
		}
	}
	return 0;
}

最后，附上例题及题解，辅助理解；

HH的项链
校门外的树
情书密码

线段树

线段树是一棵二叉搜索树，它支持上述树状数组的全部操作，并支持树状数组外的其它例如求区间最值等的操作，既支持在线操作，也支持离线操作；

线段树与树状数组对比：

优点：线段树适用范围广，当你正确写出板子时，其它操作就变得很简单；

缺点：板子代码量大，容易打错且不易察觉；

常数比树状数组大；

查错麻烦（由于使用递归形式建树及更新值）；

线段树的每个点存储的是一段区间的信息，每个节点的编号是普通二叉树的编号；

所以，对于一个节点x，其左儿子的编号为x << 1；其右儿子的编号为(x << 1) + 1（或者写成更快的位运算x << 1 | 1，因为x << 1为偶数，x << 1 | 1就相当于(x << 1) + 1；

设节点x管辖区间为(l, r)，则定义左儿子管辖区间为(l, mid)，右儿子管辖区间为(mid + 1, r)；

对于一棵二叉树，我们通常使用递归形式建树，先从根节点出发分别递归左右儿子，最后回溯时更新值；

线段树同理，我们使用递归形式建树，先从根节点出发分别递归左右儿子，最后回溯时更新值（一般为区间最值和区间和）；

首先开一个结构体储存该点的区间左右端点，以及区间最值和区间和；

点击查看代码 
struct sss{
	int l, r, ma, sum; //左端点，右端点，区间最大值，区间和；
}tr[50000005]; //要开至少4倍空间，防炸；

建树部分代码：

点击查看代码 
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}

建完了树，开始操作；

1.单点修改，区间查询；

这个挺简单；

模板题

点击查看代码 
#include <iostream>
#include <string>
using namespace std;
int n, m;
string s;
int a[100005];
struct sss{
	int l, r, ma, sum; //左端点，右端点，区间最大值，区间和；
}tr[50000005]; //要开4倍空间；
int ls(int x) { //x的左孩子编号；
	return x << 1;
}
int rs(int x) { //x的右孩子编号；
	return x << 1 | 1;
}
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void add_dian(int id, int x, int k) { //单点修改，将位置为x的数加上k（id为现在找到的点编号）；
	if (tr[id].l == tr[id].r) {
		tr[id].ma = k;
		tr[id].sum += k; //加k操作； 
		return;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	add_dian(x <= mid ? ls(id) : rs(id), x, k); //看看x在左子树还是右子树（注意中点在左子树）；
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum; //更新每个sum值；
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
int ask_sum(int id, int l, int r) { //查询区间(l, r)的和（id为现在找的点的编号）；
	if (tr[id].l >= l && tr[id].r <= r) {
		return tr[id].sum; //如果区间正好被包含就不用找了；
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return ask_sum(ls(id), l, r);
	else if (l > mid) return ask_sum(rs(id), l, r);
	else return ask_sum(ls(id), l, mid) + ask_sum(rs(id), mid + 1, r);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n != 0) bt(1, 1, n);
	cin >> m;
	int k, d;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		cin >> k >> d;
		if (s == "ADD") {
			add_dian(1, k, d);
		}
		else if (s == "SUM") {
			cout << ask_sum(1, k, d) << endl;
		}
	}
	return 0;
}

2.区间修改，区间查询及单点查询；

对于区间修改，如果要全部修改的话，从该区间开始要一直修改到根，会TLE；

怎么办呢？

我们引入一个新的东西：懒惰标记；

所谓懒惰标记，即在更新时只更新到管辖此更新区间的子树的根，并将此根的懒惰标记 += 要更新的值，等查询时在下放标记更新它的子节点，这样就可以减少许多不必要的操作，进而避免TLE；

具体更新操作见下面的题；

对于后面的查询，单点查询可以理解成区间长度为1的查询，每次查询从mid递归寻找原区间，最后将答案合并即为最终答案；

模板题

点击查看代码 
#include <iostream> //要开long long, long long, long long!!!!!!!!!!!!!!!!!!!；
#include <string>
using namespace std;
int n, m;
string s;
long long a[10000005];
struct sss{
	int l, r;
	long long ma, sum, lazy; //左端点，右端点，区间最大值，区间和，懒惰标记；long long, long long, long long!!!!!!!!!!!!!!!!!!!!!!!!!；
}tr[50000005]; //要开4倍空间；
int ls(int x) { //x的左孩子编号；
	return x << 1;
}
int rs(int x) { //x的右孩子编号；
	return x << 1 | 1;
}
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void push_down(int id) { //下放标记；
	tr[ls(id)].lazy += tr[id].lazy;
	tr[rs(id)].lazy += tr[id].lazy;
	tr[ls(id)].sum += tr[id].lazy * (tr[ls(id)].r - tr[ls(id)].l + 1);
	tr[rs(id)].sum += tr[id].lazy * (tr[rs(id)].r - tr[rs(id)].l + 1); //sum存储区间总和；
	tr[id].lazy = 0;
}
void add(int id, int a, int b, int l, int r, int k) { //区间修改，将区间(l, r)加k；
	if (l > b || r < a) return;
	if (a >= l && b <= r) {
		tr[id].sum += k * (b - a + 1);
		tr[id].lazy += k;
		return;
	}
	int mid = (a + b) >> 1; //以修改区间为基准，找被修改区间（原区间）；
	push_down(id);
	add(ls(id), a, mid, l, r, k);
	add(rs(id), mid + 1, b, l, r, k);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
}
long long ask_he(int id, int a, int b, int l, int r) { //区间(l, r)查询和；
	if (a > r || b < l) return 0;
	if (a >= l && b <= r) return tr[id].sum;
	int mid = (a + b) >> 1; //同上；
	push_down(id);
	return ask_he(ls(id), a, mid, l, r) + ask_he(rs(id), mid + 1, b, l, r);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n != 0) bt(1, 1, n);
	cin >> m;
	int k, d, c;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		if (s == "ADD") {
			cin >> k >> d >> c;
			add(1, 1, n, k, d, c);
		} else if (s == "QUERY") {
			cin >> k;
			cout << ask_he(1, 1, n, k, k) << endl;
		}
	}
	return 0;
}

模板题

点击查看代码 
#include <iostream> //要开long long, long long, long long!!!!!!!!!!!!!!!!!!!；
#include <string>
using namespace std;
int n, m;
string s;
long long a[10000005];
struct sss{
	int l, r;
	long long ma, sum, lazy; //左端点，右端点，区间最大值，区间和，懒惰标记；long long, long long, long long!!!!!!!!!!!!!!!!!!!!!!!!!；
}tr[50000005]; //要开4倍空间；
int ls(int x) { //x的左孩子编号；
	return x << 1;
}
int rs(int x) { //x的右孩子编号；
	return x << 1 | 1;
}
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void push_down(int id) { //下放标记；
	tr[ls(id)].lazy += tr[id].lazy;
	tr[rs(id)].lazy += tr[id].lazy;
	tr[ls(id)].sum += tr[id].lazy * (tr[ls(id)].r - tr[ls(id)].l + 1);
	tr[rs(id)].sum += tr[id].lazy * (tr[rs(id)].r - tr[rs(id)].l + 1); //sum存储区间总和；
	tr[id].lazy = 0;
}
void add(int id, int a, int b, int l, int r, int k) { //区间修改，将区间(l, r)加k；
	if (l > b || r < a) return;
	if (a >= l && b <= r) {
		tr[id].sum += k * (b - a + 1);
		tr[id].lazy += k;
		return;
	}
	int mid = (a + b) >> 1; //以修改区间为基准，找被修改区间（原区间）；
	push_down(id);
	add(ls(id), a, mid, l, r, k);
	add(rs(id), mid + 1, b, l, r, k);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
}
long long ask_he(int id, int a, int b, int l, int r) { //区间(l, r)查询和；
	if (a > r || b < l) return 0;
	if (a >= l && b <= r) return tr[id].sum;
	int mid = (a + b) >> 1; //同上；
	push_down(id);
	return ask_he(ls(id), a, mid, l, r) + ask_he(rs(id), mid + 1, b, l, r);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n != 0) bt(1, 1, n);
	cin >> m;
	int k, d, c;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		cin >> k >> d;
		if (s == "ADD") {
			cin >> c;
			add(1, 1, n, k, d, c);
		} else if (s == "SUM") {
			cout << ask_he(1, 1, n, k, d) << endl;
		}
	}
	return 0;
}

总模板

点击查看代码 
#include <iostream> //要开long long, long long, long long!!!!!!!!!!!!!!!!!!!； 
#include <string>
using namespace std;
int n, m;
string s;
long long a[10000005];
struct sss{
	int l, r;
	long long ma, sum, lazy; //左端点，右端点，区间最大值，区间和，懒惰标记；long long, long long, long long!!!!!!!!!!!!!!!!!!!!!!!!!；
}tr[50000005]; //要开4倍空间；
int ls(int x) { //x的左孩子编号；
	return x << 1;
}
int rs(int x) { //x的右孩子编号；
	return x << 1 | 1;
}
void bt(int id, int l, int r) {
	tr[id].l = l;
	tr[id].r = r;
	if (l == r) {
		tr[id].ma = a[l];
		tr[id].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	bt(ls(id), l, mid);
	bt(rs(id), mid + 1, r);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void add_dian(int id, int x, int k) { //单点修改，将位置为x的数加上k（id为现在找到的点编号）；
	if (tr[id].l == tr[id].r) {
		tr[id].ma = k;
		tr[id].sum += k; //加k操作；
		return;
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	add_dian(x <= mid ? ls(id) : rs(id), x, k); //看看x在左子树还是右子树（注意中点在左子树）；
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum; //更新每个sum值；
	tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
long long ask_sum(int id, int l, int r) { //查询区间(l, r)的和（id为现在找的点的编号）；
	if (tr[id].l >= l && tr[id].r <= r) {
		return tr[id].sum; //如果区间被包含就不用找了；
	}
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return ask_sum(ls(id), l, r);
	else if (l > mid) return ask_sum(rs(id), l, r);
	else return ask_sum(ls(id), l, mid) + ask_sum(rs(id), mid + 1, r);
}
void push_down(int id) { //下放标记；
	tr[ls(id)].lazy += tr[id].lazy;
	tr[rs(id)].lazy += tr[id].lazy;
	tr[ls(id)].sum += tr[id].lazy * (tr[ls(id)].r - tr[ls(id)].l + 1);
	tr[rs(id)].sum += tr[id].lazy * (tr[rs(id)].r - tr[rs(id)].l + 1); //sum存储区间总和；
	tr[id].lazy = 0;
}
void add(int id, int a, int b, int l, int r, int k) { //区间修改，将区间(l, r)加k；
	if (l > b || r < a) return;
	if (a >= l && b <= r) {
		tr[id].sum += k * (b - a + 1);
		tr[id].lazy += k;
		return;
	}
	int mid = (a + b) >> 1; //以修改区间为基准，找被修改区间（原区间）；
	push_down(id);
	add(ls(id), a, mid, l, r, k);
	add(rs(id), mid + 1, b, l, r, k);
	tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
}
long long ask_he(int id, int a, int b, int l, int r) { //区间(l, r)查询和；
	if (a > r || b < l) return 0;
	if (a >= l && b <= r) return tr[id].sum;
	int mid = (a + b) >> 1; //同上；
	push_down(id);
	return ask_he(ls(id), a, mid, l, r) + ask_he(rs(id), mid + 1, b, l, r);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n != 0) bt(1, 1, n);
	cin >> m;
	int k, d, c;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		if (s == "ADD") {
			cin >> k >> d >> c;
			add(1, 1, n, k, d, c);
		} else if (s == "QUERY") {
			cin >> k;
			cout << ask_he(1, 1, n, k, k) << endl;
		}
	}
	return 0;
}

还有一篇写的不错的博客，可以参考参考（里面的图画的非常详细）；、

线段树这东西很难调，一定一定要自己静下心来调；

标签：树状,int,线段,tr,long,详解,ls,sum,id
From： https://www.cnblogs.com/PeppaEvenPig/p/18020355

相关文章

  • Java注解篇之@SuppressWarnings注解详解 代码编译通过且可以运行，但每行前面的“感叹号
    Java注解篇之@SuppressWarnings注解详解@SuppressWarnings作用：用于抑制编译器产生警告信息。它的注解目标为类、字段、函数、函数入参、构造函数和函数的局部变量，但是建议注解声明在最接近警告发生的位置。去感叹号？我们经常遇到代码编译通过且可以运行，但每行前面的“感叹号”就......
  • HH项链(树状数组)
    HH项链题目描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难......
  • 树状数组
    树状数组是一种支持\(O(\logn)\)时间内进行单点修改和区间查询的，代码量小的数据结构。原理及实现下为洛谷P3374【模板】树状数组1题意简述：已知一个长度为\(n\)的数列\(a\)，你需要进行下面两种操作：将某一个数加上\(x\)；求出某区间每一个数的和。保证\(......
  • 情书密码 （树状数组）
    题目问题描述有消息称：绝恋找到了自己的MissRight，正准备自己的表白。绝恋已经写好了情书，但为了避免其它人截获，他对情书进行加密。为了打探绝恋的私密，你冒着生命危险终于搞到了这封情书。原以为可以轻易将情书解密，结果竟然发现聪明的绝恋并没有直接写出加密用的密码，而是在那粉红......
  • 学习笔记#4：树状数组和 LIS
    学习笔记#4：树状数组和LIS前言：树状数组是和线段树类似的数据结构，更确切的说，树状数组能解决的问题，线段树都能解决，而线段树还能解决一些树状数组所不能解决的问题。因此线段树的应用范围比树状数组更广泛。但是，树状数组的常数更小，在同样的\(\text{O}(n\logn)\)复杂度下，树状数......
  • 树状数组
    HH的项链看到这题，我首先想到了用flag[]数组标记，很明显这是必需的。但随着代码进行，又会遇到一个问题：如1212，如果按照正常标记后面两个就不会被标记，那遍历3到4时，结果为0。顺着思路想，如果我们在用完一次后把它丢掉，重新遍历，这也就导致我们必须要采用一种有序遍历，从而让后面的更......
  • VB Open 函数详解 打开、关闭、读、写文件
    （一）打开和关闭文件    1、顺序文件    打开顺序文件，我们可以使用Open语句。它的格式如下：OpenpathnameFor[Input|Output|Append]As[#]filenumber[Len=buffersize]     说明：    （1）参数pathname表示要打开的文件名，文件名可以包含有驱动器和目录 ......
  • 【c&c++】cJSON详解
    一、JSON概述1.1JSON介绍JSON：JavaScript对象表示法（JavaScriptObjectNotation）。是一种轻量级的数据交换格式。它基于ECMAScript的一个子集。JSON采用完全独立于语言的文本格式，但是也使用了类似C语音家族的习惯（包括C、C++、C#、Java、JavaScript、Perl、Python等）。这些特性使JSON......
  • 树状数组
    从这边抄（借鉴）的这是一个完整的二叉树把它变成直角三角形下面用一维数组对应删掉多余的叶子这个就是树状数组......
  • 【机器学习】机器学习常见算法详解第4篇：KNN算法计算过程（已分享，附代码）
    本系列文章md笔记（已分享）主要讨论机器学习算法相关知识。机器学习算法文章笔记以算法、案例为驱动的学习，伴随浅显易懂的数学知识，让大家掌握机器学习常见算法原理，应用Scikit-learn实现机器学习算法的应用，结合场景解决实际问题。包括K-近邻算法，线性回归，逻辑回归，决策树算法，集成学习，聚......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99