菜鸡求助线段树
  • 板块灌水区
  • 楼主pengziyippp
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/21 13:32
  • 上次更新2023/11/21 17:54:51
查看原帖
菜鸡求助线段树
845330
pengziyippp楼主2023/11/21 13:32

线段树看了个半懂
有没有好心人帮我写个代码解释(就是注释)
悬赏

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int tree[N << 2], tag[N << 2], a[N];
void push_down(int p, int l ,int r) {
	if (tag[p]) {
		int mid = l + r >> 1;
		tree[p << 1] += (mid - l + 1) * tag[p];
		tag[p << 1] += tag[p];
		tree[p << 1 | 1] += (r - mid - 1 + 1) * tag[p];
		tag[p << 1 | 1] += tag[p];
		tag[p] = 0;
	}
}
void build (int p, int l, int r) {
	if (l == r) {
		tree[p] = a[l];
		return ;
	}
	int mid = l + r >> 1;
	build (p << 1, l, mid);
	build (p << 1 | 1, mid + 1, r);
	tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
void update (int p, int pl ,int pr, int l, int r, int k) {
	if (pl >= l && pr <= r) {
		tree[p] += k * (pr - pl + 1);
		tag[p] += k;
		return;
	}
	int mid = pl + pr >> 1;
	push_down(p, pl, pr);
	if (l <= mid) update (p << 1, pl, mid, l, r, k);
	if (r > mid) update (p << 1 | 1, mid + 1, pr, l, r, k);
	tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
int query (int p, int pl, int pr, int l, int r) {
	if (pl >= l && pr <= r) return tree[p];
	int mid = pl + pr >> 1;
	push_down(p, pl, pr);
	int res = 0;
	if (l <= mid) res += query(p << 1, pl ,mid, l, r);
	if (r > mid) res += query(p << 1 | 1, mid + 1, pr, l, r);
	tree[p] = tree[p << 1] + tree[p << 1 | 1];
	return res;
}
signed main () {
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= n ; i ++) cin >> a[i];
	build(1, 1, n);
	while (m --) {
		int op;
		cin >> op;
		int l, r, k;
		if (op == 1) {
			cin >> l >> r >> k;
			update (1, 1, n, l, r, k);
		}
		else {
			cin >> l >> r;
			cout << query(1, 1, n, l, r) << '\n';
		}
	}
	return 0;
}
2023/11/21 13:32
加载中...