Hướng dẫn giải của [CSES 2166] Prefix 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.
Một cây phân đoạn tổng/tối đa đơn giản sẽ không đủ cho bài toán này. Chúng ta cần lưu trữ thêm thông tin trong các nút.
Đối với mỗi nút, chúng ta sẽ lưu tổng các giá trị trong đoạn tương ứng với nút đó và cả tổng tiền tố lớn nhất của các giá trị đó.
Một hàm truy vấn thông thường sẽ không hoạt động vì chúng ta phải theo dõi tổng tiền tố. Với mục đích này, hai biến được sử dụng:
- ~\texttt{prefix\\_sum}~, biến này sẽ được sử dụng bởi con trỏ trái, tích lũy tổng tiền tố từ bên trái. Nó sẽ giữ tổng các giá trị từ đầu đoạn truy vấn đến đầu nút hiện tại.
- ~\texttt{subfix\\_sum}~, biến này sẽ được sử dụng bởi con trỏ phải. Chúng ta không thể tích lũy tổng khi di chuyển vì con trỏ phải bắt đầu từ cuối cùng của đoạn truy vấn. Do đó, tổng cần được tính trước và con trỏ phải sẽ trừ dần từ nó khi di chuyển lên trong cây.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int TREE_SIZE = 1 << 18;
struct Node {
ll sum;
ll max_prefix;
} tree[TREE_SIZE * 2];
Node merge(Node l, Node r) {
return {l.sum + r.sum, max(l.max_prefix, l.sum + r.max_prefix)};
}
void change(int i, int x) {
i += TREE_SIZE;
tree[i] = {x, x};
while (i > 1) {
i /= 2;
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
}
// Trả về tổng các giá trị trong đoạn [l, r]
ll query_sum(int l, int r) {
ll sum = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) sum += tree[l++].sum;
if (r % 2 == 0) sum += tree[r--].sum;
l /= 2;
r /= 2;
}
return sum;
}
// Trả về tổng tiền tố lớn nhất trong đoạn [l, r]
ll query(int l, int r) {
ll prefix_sum = 0;
ll subfix_sum = query_sum(l, r);
ll res = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) {
res = max(res, prefix_sum + tree[l].max_prefix);
prefix_sum += tree[l].sum;
l++;
}
if (r % 2 == 0) {
subfix_sum -= tree[r].sum;
res = max(res, subfix_sum + tree[r].max_prefix);
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 << query(l, r) << '\n';
}
}
}
Chương trình tham khảo
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int TREE_SIZE = 1 << 18;
struct Node {
ll sum;
ll max_prefix;
} tree[TREE_SIZE * 2];
Node merge(Node l, Node r) {
return {l.sum + r.sum, max(l.max_prefix, l.sum + r.max_prefix)};
}
void change(int i, int x) {
i += TREE_SIZE;
tree[i] = {x, x};
while (i > 1) {
i /= 2;
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
}
// Returns the sum of the value in range [l, r]
ll query_sum(int l, int r) {
ll sum = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) sum += tree[l++].sum;
if (r % 2 == 0) sum += tree[r--].sum;
l /= 2;
r /= 2;
}
return sum;
}
// Returns the maximum prefix sum in range [l, r]
ll query(int l, int r) {
ll prefix_sum = 0;
ll subfix_sum = query_sum(l, r);
ll res = 0;
l += TREE_SIZE;
r += TREE_SIZE;
while (l <= r) {
if (l % 2 == 1) {
res = max(res, prefix_sum + tree[l].max_prefix);
prefix_sum += tree[l].sum;
l++;
}
if (r % 2 == 0) {
subfix_sum -= tree[r].sum;
res = max(res, subfix_sum + tree[r].max_prefix);
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 << query(l, r) << '\n';
}
}
}
Bình luận