Hướng dẫn giải của [CSES 1648] Dynamic Range Sum Queries
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Vì các giá trị không cố định, ta không thể sử dụng bảng thưa (sparse table). Tuy nhiên, cây phân đoạn xử lý các truy vấn cập nhật mà không gặp khó khăn.
#include <iostream>
using namespace std;
using ll = long long;
const int TREE_SIZE = 1 << 18;
ll tree[TREE_SIZE * 2];
void change(int i, int x) {
i += TREE_SIZE;
tree[i] = x;
while (i > 1) {
i /= 2;
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
// Returns the sum of values in range [l, r]
ll get_sum(int l, int r) {
ll res = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) res += tree[l++];
if (r % 2 == 0) res += tree[r--];
l /= 2;
r /= 2;
}
return res;
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
change(i, x);
}
for (int qi = 0; qi < q; ++qi) {
int t;
cin >> t;
if (t == 1) {
int k, u;
cin >> k >> u;
change(k, u);
} else {
int l, r;
cin >> l >> r;
cout << get_sum(l, r) << '\n';
}
}
}
Chương trình tham khảo
#include <iostream>
using namespace std;
using ll = long long;
const int TREE_SIZE = 1 << 18;
ll tree[TREE_SIZE * 2];
void change(int i, int x) {
i += TREE_SIZE;
tree[i] = x;
while (i > 1) {
i /= 2;
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
// Returns the sum of values in range [l, r]
ll get_sum(int l, int r) {
ll res = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) res += tree[l++];
if (r % 2 == 0) res += tree[r--];
l /= 2;
r /= 2;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
change(i, x);
}
for (int qi = 0; qi < q; ++qi) {
int t;
cin >> t;
if (t == 1) {
int k, u;
cin >> k >> u;
change(k, u);
} else {
int l, r;
cin >> l >> r;
cout << get_sum(l, r) << '\n';
}
}
}
Bình luận