【模板】单点更新，区间求和

0

liangsheng LV 3 SU @ 2025-9-13 11:26:59

线段树实现，PPT 上的写法

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
	int n;
	vector<int> t;
	
	SegmentTree(int n_) {
		n = n_;
		t.assign(n * 2, 0);
	}
	
	// 把原数组的 a[p] += v;
	void update(int p, int v) {
		p += n;  // 把 p 变成 t 中的编号
		t[p] += v;
		for (int i = p / 2; i >= 1; i /= 2) {
			t[i] = t[i * 2] + t[i * 2 + 1];
		}
	}
	
	// 查询原数组 a[l], a[l + 1], ... a[r] 的和
	int query(int l, int r) {
		l += n, r += n;  // 把 l, r 变成 t 数组的下标
		int ans = 0;
		while (l <= r) {
			if (l % 2 == 1) ans += t[l], l++;
			if (r % 2 == 0) ans += t[r], r--;
			l /= 2, r /= 2;
		}
		return ans;
	}
};

int main() {
	int n, m, x, cmd, l, r, p;
	cin >> n >> m;
	SegmentTree seg(n);
	for (int i = 0; i < n; i++) {
		cin >> x;
		seg.update(i, x);  // 单点更新
	}
	
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> p >> x;
			seg.update(p - 1, x);  // 单点更新
		} else {
			cin >> l >> r;
			cout << seg.query(l - 1, r - 1) << '\n';
		}
	}
	
	return 0;
}

0

liangsheng LV 3 SU @ 2025-9-12 10:30:17

用自底向上的非递归线段树实现
AC，100 分，同样又快又好写，同时可扩展性强，推荐！
这里是用位操作优化后的简洁写法，如果不是很明白，可以参考老师 PPT 上的写法

// 参考资料
// https://blog.csdn.net/weixin_43960287/article/details/108246164
// https://www.luogu.com.cn/article/pfhvnr5i

#include <bits/stdc++.h>
using namespace std;

// https://leetcode.cn/contest/weekly-contest-399/ranking/
// 第一名 fmota 的 D 题
template<typename T>
struct segtree {
	vector<T> t;
	int n;
	segtree(int n): n(n) {
		t.assign(2 * n, T());  // 注意不同的问题, 初值不一样!!
	}
	
	// 将原数组中 a[p] 赋值为 v, a[p] = v
	void update(int p, T v) {
		for (t[p += n] = v; p >>= 1; ) t[p] = t[p << 1] + t[p << 1 | 1];
	}
	
	// 将原数组中 a[p] 加上 v, a[p] += v
	void add(int p, T v) {

		for (t[p += n] += v; p >>= 1; ) t[p] = t[p << 1] + t[p << 1 | 1];
		
//	    相当于下面 4 句话
//		p += n;     // 找到原数组的 a[p] 在线段树中对应的位置
//		t[p] += v;  // 把线段树中的节点 +v
//		p /= 2;     // 找到 p 的上层节点
//		while (p > 0) t[p] = t[p * 2] + t[p * 2 + 1], p /= 2;  //合并节点的值
	}
	
	// 询问原数组 a[l] 到 a[r - 1] 的和, 从 0 开始编号 
	T query(int l, int r) {
		T ans = T();
		for (l += n, r += n; l < r; l >>= 1, r >>= 1){
			if (l & 1) ans += t[l++];  // 如果 l 是奇数, 直接加上 t[l]
			if (r & 1) ans += t[--r];  // 如果 r 是奇数, 直接加上 t[r - 1]
		}
		return ans;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, x, y, z;
	cin >> n >> m;
	segtree<int> seg(n);
	for (int i = 0; i < n; i++) {
		cin >> x;
		seg.update(i, x);  // 从 0 开始编号
	}
	
	while (m--) {
		cin >> x >> y >> z;
		if (x == 1) seg.add(y - 1, z);             // 从 0 开始编号
		else cout << seg.query(y - 1, z) << '\n';  // 左闭右开
	}
	
	return 0;
}

0

liangsheng LV 3 SU @ 2025-8-12 17:01:06

最牛逼的方法，树状数组， $O(m \times log(n))$
AC，100 分，又快又好写！！

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

template <typename T>  // 使用 template 模板, 用法见定义
struct Fenwick {
	int n;
	vector<T> a;
	
	Fenwick(int n_) : n(n_) {
		// 注意: 树状数组都是从 1 开始编号 a[1..n], 不要从 0 开始
		// 相当于 a = vector<int>(n + 1, 0)
		a.assign(n + 1, 0);
	}
	
	// 更新操作, 不断 p += lowbit(p)
	void add(int p, T v) {
		for (; p <= n; p += p & -p) a[p] += v;
	}
	
	// 求前缀和: sum(a[1..p]), 不断 p -= lowbit(p)
	T get(int p) {
		T ans = 0;
		for (; p > 0; p -= p & -p) ans += a[p];
		return ans;
	}
	
	// 求区间和: sum(a[1..r]) - sum(a[1..(l-1)])
	T get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, x, y, z;
	cin >> n >> m;
	
	// 利用 template, 申明为 int 的树状数组
	// Fenwick<int> 可以申明为 int 的树状数组
	Fenwick<int> a(n);
	for (int i = 1; i <= n; i++) {
		cin >> x;
		a.add(i, x);
	}
	
	while (m--) {
		cin >> x >> y >> z;
		if (x == 1) a.add(y, z);           // 更新
		else cout << a.get(y, z) << '\n';  // 求前缀和
	}
	
	return 0;
}

0

liangsheng LV 3 SU @ 2025-8-12 16:49:29

方法 3：将数组分块， $O(m \times \sqrt{n})$
AC，100 分，但是代码略复杂

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, cmd, x, k, l, r;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	int d = sqrt(n);        // 每 d 个数分成一组
	int cnt = (n + 1) / d;  // 总共有 n / d 组
	
	vector<int> b(n + 1, 0);  // b[i]: a[i] 属于哪一组
	for (int i = 1, j = 1; i <= n; i++) {
		b[i] = j;
		if (i % d == 0) j++;
	}
	
	vector<int> s(cnt + 1, 0);  // s[i]: 第 i 组的数的和
	for (int i = 1; i <= n; i++) s[b[i]] += a[i];
	
	// 求 a[1] + a[2] + ... + a[r]
	auto sum = [&](int r) -> int {
		if (r == 0) return 0;
		int ans = 0;
		
		// r 前面整组的和
		for (int i = 1; i < b[r]; i++) ans += s[i];  // O(n / d)
		
		// r 所在的组的前部分的和
		for (int i = d * (b[r] - 1) + 1; i <= r; i++) ans += a[i];  // O(d)
		return ans;
	};
	
	// O(m * n)
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> x >> k;
			a[x] += k, s[b[x]] += k;  // O(1))
		} else {
			cin >> l >> r;
			cout << sum(r) - sum(l - 1) << '\n';
		}
	}
	
	return 0;
}

0

liangsheng LV 3 SU @ 2025-8-12 16:48:15

方法 2：维护前缀和， $O(m \times n)$
TLE，70 分

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, cmd, x, k, l, r;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	// f[i] = sum(a[1] + a[2] + ... + a[i])
	vector<int> f(n + 1, 0);
	for (int i = 1; i <= n; i++) f[i] = f[i - 1] + a[i];
	
	// O(m * n)
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> x >> k;
			for (int i = x; i <= n; i++) f[i] += k;  // O(n)
		} else {
			cin >> l >> r;
			cout << f[r] - f[l - 1] << '\n';  // O(1)
		}
	}
	
	return 0;
}

0

liangsheng LV 3 SU @ 2025-8-12 16:47:26

方法 1：直接模拟， $O(m \times n)$
TLE，70分

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, cmd, x, k, l, r;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	// O(m * n)
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> x >> k;
			a[x] += k;  // O(1)
		} else {
			cin >> l >> r;
			int ans = 0;
			for (int i = l; i <= r; i++) ans += a[i];  // O(n)
			cout << ans << '\n';
		}
	}
	
	return 0;
}

6 条题解

信息

状态

开发

支持

关于