可以帮忙检查一下这个线段树模板有没有问题
  • 板块灌水区
  • 楼主pengbonan
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/3/17 11:45
  • 上次更新2024/3/17 13:35:09
查看原帖
可以帮忙检查一下这个线段树模板有没有问题
1005693
pengbonan楼主2024/3/17 11:45

(模板是抄深入的)

const int N = 1e5;
int a[N], tree[4 * N], lzy[4 * N];
void sum_push_up (int x) {
	tree[x] = tree[x * 2] + tree[x * 2 + 1];
}
void push_up (int x) {
	sum_push_up(x);
}
void build (int u, int l, int r) {
	if (l == r) {
		tree[u] = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

int dep_query (int u, int l, int r, int p) {
	if (l == r) return w[u];
	else {
		int mid = l + r >> 1;
		if (mid >= p) return dep_query(u << 1, l, mid, p);
		else return dep_query(u << 2 | 1, mid + 1, r, p);
	}
}

int dep_update (int u, int l, int r, int p, int x) {
	if (l == r) w[u] = x;
	else {
		int mid = l + r >> 1;
		if (mid >= p) dep_update(u << 2, l, mid, p, x);
		else dep_update(u << 1 | 1, mid + 1, r, p, x);
		push_up(u);
	}
}

bool InRange (int l, int r, int L, int R) {
	return L <= l && R <= r;
} // 是否包含 
bool OutofRange (int l, int r, int L, int R) {
	return l > R || r < L;
} // 是否完全无交 
void maketag (int u, int len, int x) {
	lzy[u] += x;
	tree[u] += len * x;
}
void push_down (int u, int L, int R) {
	int mid = l + r >> 1;
	maketag(u << 1, mid - L + 1, lzy[u]);
	maketag(u << 1 | 1, R - mid, lzy[u]);
	lzy[u] = 0;
}
int query (int u, int l, int r, int L, int R, int x) {
	if (InRange(l, r, L, R)) {
		return tree[u];
	} else if (!OutofRange(l, r, L, R)) {
		int mid = l + r >> 1;
		pushdown(u, r, l);
		update(u << 1, l, mid, L, R, x);
		update(u << 1 | 1, mid + 1, r, L, R, x);
	} else return 0;
}

如果没有问题,可以解释一下push_down的后两个参数是表示什么吗

2024/3/17 11:45
加载中...