Cây phân đoạn - Segment Tree
Link: https://vnoi.info/wiki/algo/data-structures/segment-tree-basic.md
Bài toán:
BÀI TOÁN ÁP DỤNG
Tổng đoạn Cho một dãy số a0 , a1 , a2 ,…, an-2 , an-1 là các số nguyên |ai |≤2.109. Ban đầu tất cả các số có giá trị 0 và trên dãy số có thể thực hiện hai lệnh sau:
Lệnh cập nhật S(i, k):
Gán giá trị k cho phần tử ai (0≤ 𝑖 ≤ 𝑛 − 1; |𝑘| ≤2.109 ).
Lệnh truy vấn Q(i, j):
Cho biết tổng của các số ai , ai+1 ,…, aj-1 , aj (0≤ 𝑖 ≤ 𝑗 ≤ 𝑛 − 1).
Yêu cầu: Cho một dãy m lệnh thuộc một trong hai loại trên, hãy trả lời tất cả các lệnh truy vấn.
Dữ liệu: Vào từ file văn bản Sum.inp
Dòng 1 chứa hai số nguyên dương n, m≤105 .
m dòng tiếp theo, mỗi dòng chứa thông tin về một lệnh, đầu tiên là một ký tự ∈ {S, Q}. Nếu ký tự đầu dòng là S, tiếp theo là hai số nguyên i, k cho biết đó là lệnh S(i, k). Nếu ký tự đầu dòng là Q, tiếp theo là hai số nguyên i, j cho biết lệnh Q(i , j).
Kết quả: Ghi ra file văn bản Sum.out
Tương ứng với mỗi lệnh truy vấn Q trong file dữ liệu, ghi ra trên một dòng một số nguyên là trả lời cho truy vấn đó.
VÍ DỤ:
Sum.inp
5 6
S 2 1
S 4 5
Q 2 4
S 3 6
S 2 7
Q 1 4
Sum.out
6
18
Code:
#include <iostream>
using namespace std;
int a[1000], st[1000];
void update (int v, int tl, int tr, int pos, int new_val) {
a[pos]=new_val;
if (tl == tr) st[v] = new_val;
else {
int mid = (tl + tr) / 2;
if (pos <= mid) update (v*2 + 1, tl, mid, pos, new_val);
else update (v*2 + 2, mid+1, tr, pos, new_val);
st[v] = st[v*2 + 1] + st[v*2 + 2];
}
}
int getSum (int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l >= tl && r <= tr) return st[v];
int mid = (tl + tr) / 2;
return getSum (v*2 + 1, tl, mid, l, r) + getSum (v*2 + 2, mid+1, tr, l, r);
}
int main()
{
int n, m, i, ii, x, y, pos;
string Str, Cmd;
cout << "Nhap n va m" << endl;
cin >> n >> m;
fflush(stdin);
for (i=1; i<=m; i++) {
getline(cin, Str);
Cmd=Str.substr(0,1);
Str.erase(0,2);
pos=Str.find(" ");
x=stoi(Str.substr(0, pos));
Str.erase(0,pos);
y=stoi(Str);
cout << "x " << x << ", y " << y << endl;
if (Cmd=="S")
update(1, 1, n, x, y);
else
cout << getSum(1, 1, n, x, y) << endl;
for (ii=1; ii<=n; ii++)
cout << a[ii] << " ";
cout << endl;
}
return 0;
}