P3372线段树求助(悬关)
  • 板块学术版
  • 楼主vincent_one
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/10/20 11:00
  • 上次更新2023/11/2 12:37:09
查看原帖
P3372线段树求助(悬关)
302008
vincent_one楼主2023/10/20 11:00

求助大佬,我这样写线段树有什么问题吗?

代码:

#include <bits/stdc++.h>
#define fr first
#define sc second
#define N 100010
#define mod 998244353
#define inf 2147483647
#define ll long long
using namespace std;
struct Node {
	ll w;
	int l, r;
} tr[2 * N];
int n, a[N], m;
ll build(int u, int L, int R) {
	tr[u].l = L; tr[u].r = R;
	if (L == R) {
		tr[u].w = a[L];
		return a[L];
	}
	int mid = (L + R) >> 1;
	tr[u].w = build(u * 2, L, mid) + build(u * 2 + 1, mid + 1, R);
}
void modify(int u, int x, int L, int R) {
	if (L <= tr[u].l && tr[u].r <= R) {
		tr[u].w += x * (tr[u].r - tr[u].l + 1);
		return;
	} else if (!(L > tr[u].r || R < tr[u].l)) {
		modify(u * 2, x, L, R);
		modify(u * 2 + 1, x, L, R);
		tr[u].w = tr[u * 2].w + tr[u * 2 + 1].w;
	}
}
ll Query(int u, int L, int R) {
	if (L <= tr[u].l && tr[u].r <= R) return tr[u].w;
	else if (L > tr[u].r || R < tr[u].l) return 0;
	else return Query(u * 2, L, R) + Query(u * 2 + 1, L, R);
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	while (m--) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1) {
			int k;
			cin >> k;
			modify(1, k, x, y);
		} else {
			cout << Query(1, x, y) << '\n';
		}
	}
	return 0;
}
2023/10/20 11:00
加载中...