Đồ án thuật toán cây phân đoạn Segment Tree
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (168.6 KB, 23 trang )
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN HỌC
BÁO CÁO ĐỒ ÁN CHUYÊN NGÀNH
ĐỀ TÀI:
TÌM HIỂU VỀ CÂY PHÂN ĐOẠN
GVHD: Phạm Anh Phương
SVTD: Nguyễn Ngọc Nhi - 17CNTT1
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
MỤC LỤC
PHẦN MỞ ĐẦU
1. Lý do chon đề tài.
Với sự phát triển của khoa học kỹ thuật, cơng nghệ thơng tin nói chung và
bộ môn cấu trúc dữ liệu và giải thuật nói riêng ngày càng được ứng dụng rộng rãi
trong nhiều lĩnh vực. Với một cơ sỡ dữ liệu khổng lồ, việc đưa ra một phương pháp
nhằm giải quyết vấn đề có cách hiệu quả và nhanh chống ln được sự quan tâm
của các nhà phát triển phần mềm. Thông thường dữ liệu được biểu diễn dưới dạng
danh sách liên kết. Với việc truy xuất dữ liệu chưa đạt hiệu quả cao. Sử dụng cấu
trúc dữ liệu cây là một phương pháp tăng hiệu quả cao trong các thao tác xử lý.
Vấn đề đặt ra với việc sử dụng cấu trúc dạng cây, chúng ta cần dùng giải thuật nào
với từng dạng dữ liệu để đạt hiệu quả cao nhất. Chúng ta cùng tìm hiểu phương
pháp của cây phân đoạn.
2. Mục tiêu đề tài.
Thơng qua chương trình đồ án “ Tìm hiểu về cây phân đoạn” giúp cho bản
thân trong quá trình học tập chung và tiếp cận một phương pháp mới để giải quyết
một số bài toán tin.
Dù đã dành nhiều thời gian tìm hiểu và hồn thiện bài tập nhưng chắc chắn se
khơng tránh khỏi sai sót. Em mong se nhận được những lời nhận xét và đóng góp ý kiến
từ thầy cơ để được hồn thiện hơn . . .
PHẦN I. CƠ SỞ LÝ THUYẾT CÂY PHÂN ĐOẠN
2
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
1.1 Yêu cầu giải bài toán trong tin học
Để hình dung được một bài toán tin học bạn cần thực hiện một sớ bước sau:
•
Đọc kỹ đề bài. Xây dựng một số vị dụ phản ánh được u cầu bài tốn
•
nhằm để hiểu đề.
Dùng một ngơn ngữ lập trình hoặc mã giả để thể hiện các đại lượng trong
•
bài tốn và mối quan hệ giữa các đại lượng
Chọn ra một cấu trúc dữ liệu phù hợp để biểu diễn các đối tượng
•
Dùng một ngơn ngữ lập trình để hồn thiện bài tốn. Đồng thời kiểm thử
bằng các ví dụ đã đưa ra ở bước đầu.
Xây dựng thành các hàm hay đoạn con nhằm dễ quản lý và thực hiện cải
tiến
Trước khi bước vào tìm hiểu tài liệu bạn phải có những kiến thức cơ bản sau:
1. Biết thực hiện một bài toán tin như thế nào
2. Biết đọc mã giả, sơ đồ khối là kiến thức tối thiểu ( Biết ngôn ngữ lập trình C
hoặc cao hơn là một lợi thế). Bởi vì khi trình bày vấn đề tơi sử dụng mã giã
và khi thực hiện chương trình tơi viết bằng ngơn ngữ C.
3. Tối thiểu phải đọc qua lý thuyết dưới đây và liên hệ với từng giải thích ở ví
dụ đầu tiên . Sau đó các bài sau khơng trình bày lại kiến thức căn bản và các
khái niệm.
1.2-Cây phân đoạn.
Cây phân đoạn là cấu trúc dữ liệu cho phép thực hiện các thao tác truy vấn
và cập nhật trên một đoạn các phần tử của mảng với chi phí thực hiện mỗi thao tác
có mức độ phức tạp là hàm logarit. Cây phân đoạn là một cây nhị phân đầy đủ, để
quản lý các phần trong đoạn [i..j] của mảng, cây phân đoạn được tổ chức như sau:
• Nút đầu tiên lưu thông tin đoạn [i..j].
3
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
• Nếu i
bên phải lưu thông tin đoạn [(i+j) div 2 + 1..j] .
• Nếu i=j thì nút này khơng có nút con.
ví dụ: Sau đây là cây phân đoạn quản lý đoạn [1..8]:
Nút1
[1..8]
Nút 3:
[5..8]
Nút 2:
[1..4]
:
[1..8]
Nút 4:
[1..2]
Nút 8:
[1..1]
Nút 9:
[2..2]
Nút 5:
[3..4]
Nút 10:
[3..3]
Nút 7:
[7..8]
Nút 6:
[5..6]
Nút 11:
[4..4]
Nút 12:
[1..2]
Nút 13:
[6..6]
Nút 14:
[7..7]
Mỗi nút của cây lưu trữ thông tin của một đoạn cố định. Thông tin này thường là
tổng các phần tử, giá trị lớn nhất , giá trị nhỏ nhất…của các phần tử trong đoạn.
Các nút lá của cây lưu trữ giá trị tương ứng với các phần tử của mảng.
4
Nút 15:
[8..8]
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
PHẦN II. PHÂN TÍCH VÀ THIẾT KẾ MỘT SỐ BÀI TỐN
2.1 Ví dụ cây nhị phân hồn chỉnh
Tóm tắt đề:
Cây phân đoạn được sử dụng khi chúng ta có một mảng A, thực hiện các chỉnh sửa
và truy vấn trên các đoạn liên tiếp. Ví dụ: ta có một mảng A với 105 phần tử và cần
thực hiện Q thao tác, mỗi thao tác thuộc 1 trong 2 loại:
• Thay đổi giá trị của một phần tử: Gán Ai=v.
• Tính tổng các phần tử trên đoạn bất kì: Tính Al+Al+1+...+Ar.
Input
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Output
60
Phương pháp:
Giả sử độ dài của mảng là lũy thừa của 2 thì ta được cây nhị phân hoàn
chỉnh. Khi đi từ dưới lên ta ghép cặp nút có chỉ số (2∗i,2∗i+1)(2∗i,2∗i+1) và
tổng hợp giá trị của chúng thành giá trị của nút cha có chỉ số ii. Bằng cách này, khi
tính tổng đoạn [3,11)[3,11), ta chỉ cần cộng giá trị tại các nút 19,5,12 và 26 mà
không cần phải cộng cả 8 giá trị trong đoạn
5
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Cài đặt:
const int N = 1e5; // giới hạn của mảng
int n; // kích thước mảng
int t[2 * N];
void build() { // khởi tạo cây
for (int i = n - 1; i > 0; --i)
t[i] = t[i<<1] + t[i<<1|1];
}
void modify(int p, int value) { // gán giá trị tại vị trí p
for (t[p += n] = value; p > 1; p >>= 1)
t[p>>1] = t[p] + t[p^1];
}
int query(int l, int r) { // tính tổng đoạn [l, r)
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) res += t[l++];
if (r&1) res += t[--r];
}
return res;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", t + n + i);
build();
modify(0, 1);
printf("%d\n", query(3, 11));
return 0;
}
6
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
2.2 Bài tốn Sereja and Brackets.
Tóm tắt đề:
Cho một dãy ngoặc độ dài N (N≤106), cho M truy vấn có dạng
li,ri(1≤li≤ri≤N). Yêu cầu của bài tốn là với mỗi truy vấn tìm một chuỗi con
(không cần liên tiếp) của chuỗi từ li đến ri dài nhất mà tạo thành dãy ngoặc đúng.
Lời giải:
Với mỗi nút(ví dụ như nút id, quản lý đoạn [l,r]) chúng ta lưu ba biến nguyên:
• optimal: Là kết quả tối ưu trong đoạn [l,r].
• open: Số lượng dấu ( sau khi đã xóa hết các phần tử thuộc dãy ngoặc đúng
độ dài optimal trong đoạn.
• close: Số lượng dấu ) sau khi đã xóa hết các phần tử thuộc dãy ngoặc đúng
độ dài optimal trong đoạn.
Input
Output
())(())(())(
7
11
23
12
1 12
8 12
5 11
2 10
0
0
2
10
4
6
6
Cài đăt:
Ta tạo 1 kiểu dữ liệu cho 1 nút của cây ST như sau:
7
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
struct Node {
int optimal;
int open;
int close;
Node(int opt, int o, int c) { // Khởi tạo struct Node
optimal = opt;
open = o;
close = c;
}};
Node st[MAXN * 4];
Khai báo cây ST:
Để tính thông tin ở nút id quản lý đoạn [l,r], dựa trên 2 nút con 2∗id và 2∗id+1, ta
định nghĩa 1 thao tác kết hợp 2 nút của cây ST:
Node operator + (const Node& left, const Node& right) {
Node res;
// min(số dấu "(" thừa ra ở cây con trái, và số dấu ")" thừa ra ở cây con phải)
int tmp = min(left.open, right.close);
// Để xây dựng kết quả tối ưu ở nút id, ta nối dãy ngoặc tối ưu ở 2 con, rồi thêm
// min(số "(" thừa ra ở con trái, số ")" thừa ra ở con phải).
res.optimal = left.optimal + right.optimal + tmp;
res.open = left.open + right.open - tmp;
res.close = left.close + right.close - tmp;
return res;
}
8
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
void build(int id, int l, int r) {
if (l == r) {
// Đoạn [l, r] chỉ có 1 phần tử.
if (s[l] == '(') st[id] = Node(0, 1, 0);
else st[id] = Node(0, 0, 1);
return ;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid+1, r);
st[id] = st[id * 2] + st[id * 2 + 1];
}
Node query(int id, int l, int r, int u, int v) {
if (v < l || r < u) {
// Trường hợp không giao nhau
return Node(0, 0, 0);
}
if (u <= l && r <= v) {
// Trường hợp [l, r] nằm hoàn toàn trong [u, v]
return st[id];
}
int mid = (l + r) / 2;
return query(id * 2, l, mid, u, v) + query(id * 2 + 1, mid+1, r, u, v);
}
9
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
2.3 Bài tốn KQUERY.
Tóm tắt đê:
• Cho một dãy số ai(1≤ai≤109) có N(1≤N≤30,000) phần tử
• Cho Q(1≤Q≤200,000) truy vấn có dạng 3 số ngun là li,ri,ki
(1≤li≤ri≤N,1≤k≤109).
• u cầu của bài tốn là đếm số lượng số aj(li≤j≤ri) mà aj≥k.
Phương pháp:
Giả sử chúng ta có một mảng b với bi=1 nếu ai>k và bằng 0 nếu ngược lại. Thì
chúng ta có thể dễ dàng trả lời truy vấn (i,j,k) bằng cách lấy tổng từ i đến j.
Cách làm của bài này là xử lý các truy vấn theo một thứ tự khác, để ta có thể dễ
dàng tính được mảng b. Kĩ năng này được gọi là xử lý offline (tương tự nếu ta trả
lời các truy vấn theo đúng thứ tự trong input, thì được gọi là xử lý online):
Sắp xếp các truy vấn theo thứ tự tăng dần của k.
Lúc đầu mảng b gồm toàn bộ các số 1.
Với mỗi truy vấn, ta xem trong mảng a có những phần tử nào lớn hơn giá trị k của
truy vấn trước, và nhỏ hơn giá trị k của truy vấn hiện tại, rồi đánh dấu các vị trí đó
10
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
trên mảng b thành 0. Để làm được việc này một cách hiệu quả, ta cũng cần sắp xếp
lại mảng a theo thứ tự tăng dần.
Input
5
51234
3
241
444
152
Output
2
0
3
Cài đặt:
Ta tạo kiểu dữ liệu cho truy vấn:
struct Query {
int k;
int l, r;
};
// so sánh 2 truy vấn để dùng vào việc sort.
bool operator < (const Query& a, const Query &b) {
return a.k < b.k;
}
11
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Phần xử lý chính se như sau:
vector< Query > queries; // các truy vấn
// Đọc vào các truy vấn
readInput();
// Sắp xếp các truy vấn
sort(queries.begin(), queries.end());
// Khởi tạo mảng id sao cho:
// a[id[1]], a[id[2]], a[id[3]] là mảng a đã sắp xếp tăng dần.
// Khởi tạo Segment Tree
for(Query q : queries) {
while (a[id[i]] <= q.k) {
b[id[i]] = 0;
// Cập nhật cây Segment Tree.
++i;
}
}
Vậy ta có thể viết hàm xây dựng cây như sau:
void build(int id, int l, int r) {
if (l == r) {
// Nút id chỉ gồm 1 phần tử
st[id] = 1;
return ;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2, mid+1, r);
st[id] = st[id*2] + st[id*2+1];
}
12
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Một hàm cập nhật khi ta muốn gán lại một vị trí bằng 0:
void update(int id, int l, int r, int u) {
if (u < l || r < u) {
// u nằm ngoài đoạn [l, r]
return ;
}
if (l == r) {
st[id] = 0;
return ;
}
int mid = (l + r) / 2;
update(id*2, l, mid, u);
update(id*2 + 1, mid+1, r, u);
st[id] = st[id*2] + st[id*2+1];
}
Và cuối cùng là thực hiện truy vấn lấy tổng một đoạn:
int get(int id, int l, int r, int u, int v) {
if (v < l || r < u) {
// Đoạn [l, r] nằm ngoài đoạn [u, v]
return 0;
}
if (u <= l && r <= v) {
// Đoạn [l, r] nằm hoàn toàn trong đoạn [u, v]
return st[id];
}
int mid = (l + r) / 2;
return get(id*2, l, mid, u, v)
+ get(id*2+1, mid+1, r, u, v);
}
13
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
2.4 Bài tốn KQUERY2.
Tóm tắt đề:
• Cho dãy A với N phần tử. Cần trả lời Q truy vấn.
• Có 2 loại truy vấn:
• Cập nhật: Gán Ai=v
• Truy vấn: đếm số phần tử lớn hơn k trong đoạn [l,r].
• Giới hạn:
• N≤30,000
• Ai,v≤10,000
• Q≤200,000
Bài này tương đối giống với bài KQUERY đã phân tích ở trên, tuy nhiên vì
có thao tác cập nhật, nên ta buộc phải xử lý online.
Phương pháp
Có logN nút mà ta cần xét khi trả lời truy vấn của đoạn [u,v].
Nếu trên mỗi nút chúng ta có thể lưu lại danh sách các phần tử đó theo thứ tự tăng
dần, ta có thể tìm ra kết quả ở mỗi nút bằng tìm kiếm nhị phân.
Vì thế với mỗi nút ta lưu lại một vector chứa các phần tử từ l đến r theo thứ tự tăng
dần. Điều này có thể được thực hiện với bộ phức tạp bộ nhớ là O(NlogN) do mỗi
phần tử có thể ở tối đa O(logN) nút (độ sâu của cây không quá O(logN)). Ở mỗi
nút cha có ta có thể gộp hai nút con vào nút cha bằng phương pháp giống như
Merge Sort (lưu lại hai biến chạy và so sánh lần lượt từng phần tử ở hai mảng) để
có thể xây dựng cây trong O(NlogN).
Input
Output
14
Tìm hiểu cây phân đoạn
5
51234
6
1241
0 4 10
1444
031
012
1152
GVHD: TS. Phạm Anh Phương
2
1
2
Cài đặt:
Hàm xây cây có thể được như sau:
void build(int id, int l, int r) {
if (l == r) {
// Đoạn gồm 1 phần tử. Ta dễ dàng khởi tạo nút trên ST.
st[id].push_back(a[l]);
return ;
}
int mid = (l + r) / 2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
merge(st[id*2].begin(), st[id*2].end(), st[id*2+1].begin(), st[id*2+1].end(),
st[id].begin());
}
15
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Và hàm truy vấn có thể cài đặt như sau:
int get(int id, int l, int r, int u, int v, int k) { // Trả lời truy vấn (x, y, k)
if (v < l || r < u) {
return 0;
}
if (u <= l && r <= v) {
// Đếm số phần tử > K bằng chặt nhị phân
return st[id].size()- (upper_bound(st[id].begin(), st[id].end(), k)st[id].begin());
}
int mid = (l + r) / 2;
return get(id*2, l, mid, u, v, k) + get(id*2+1, mid+1, r, u, v, k);
}
2.5 Ví dụ QMAX2
Tóm tắt đề:
Cho dãy số A với N phần tử (N≤50,000). Bạn cần thực hiện 2 loại truy vấn:
1. Cộng tất cả các số trong đoạn [l,r] lên giá trị val.
2. In ra giá trị lớn nhất của các số trong đoạn [l,r].
Phương pháp:
16
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Truy vấn đoạn [u,v]. Giả sử ta gọi F(id) là giá trị lớn nhất trong đoạn mà nút
id quản lý. Trong lúc cập nhật, muốn hàm này thực hiện với độ phức tạp khơng q
O(logN), thì khi đến 1 nút id quản lý đoạn [l,r] với đoạn [l,r] nằm hoàn toàn trong
đoạn [u,v], thì ta khơng được đi vào các nút con của nó nữa (nếu khơng độ phức
tạp se là O(N) do ta đi vào tất cả các nút nằm trong đoạn [u,v]). Để giải quyết, ta
dùng kĩ thuật Lazy Propagation như sau:
• Lưu T(id) với ý nghĩa, tất cả các phần tử trong đoạn [l,r] mà nút id quản lý
đều được cộng thêm T(id).
• Trước khi ta cập nhật hoặc lấy 1 giá trị của 1 nút id′ nào đó, ta phải đảm bảo
ta đã "đẩy" giá trị của mảng T ở tất cả các nút tổ tiên của id′ xuống id′. Để
làm được điều này, ở các hàm get và update, trước khi gọi đệ quy xuống các
con 2∗id và 2∗id+1, ta phải gán:
o T[id*2] += T[id]
o T[id*2+1] += T[id]
o T[id] = 0 chú ý ta cần phải thực hiện thao tác này, nếu không mỗi
phần tử của dãy se bị cộng nhiều lần, do ta đẩy xuống nhiều lần.
Input
Output
63
0133
0464
116
4
Cài đặt:
Ta có kiểu dữ liệu cho 1 nút của ST như sau:
struct Node {
int lazy; // giá trị T trong phân tích trên
int val; // giá trị lớn nhất.
} nodes[MAXN * 4];
17
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Hàm "đẩy" giá trị T xuống các con:
void down(int id) {
int t = nodes[id].lazy;
nodes[id*2].lazy += t;
nodes[id*2].val += t;
nodes[id*2+1].lazy += t;
nodes[id*2+1].val += t;
nodes[id].lazy = 0;
}
Hàm cập nhật:
void update(int id, int l, int r, int u, int v, int val) {
if (v < l || r < u) {
return ;
}
if (u <= l && r <= v) {
// Khi cài đặt, ta luôn đảm bảo giá trị của nút được cập nhật đồng thời với
// giá trị lazy propagation. Như vậy se tránh sai sót.
nodes[id].val += val;
nodes[id].lazy += val;
return ;
}
int mid = (l + r) / 2;
down(id); // đẩy giá trị lazy propagation xuống các con
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
nodes[id].val = max(nodes[id*2].val, nodes[id*2+1].val);
}
Hàm lấy giá trị lớn nhất:
18
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
int get(int id, int l, int r, int u, int v) {
if (v < l || r < u) {
return -INFINITY;
}
if (u <= l && r <= v) {
return nodes[id].val;
}
int mid = (l + r) / 2;
down(id); // đẩy giá trị lazy propagation xuống các con
return max(get(id*2, l, mid, u, v),
get(id*2+1, mid+1, r, u, v));
}
PHẦN III. MỐT SƠ BÀI TỒN KHÁC
3.1 Bài toán Frequent values
Đưa ra một chuỗi các n số nguyên a1 , a2 , ..., an theo thứ tự không giảm.
Ngoài ra, được cung cấp một số truy vấn bao gồm các chỉ số i và j ( 1 i ≤ j ≤ n ).
Đối với mỗi truy vấn, hãy xác định giá trị thường xuyên nhất trong số các số
nguyên ai ,..,aj..
Input
10 3
-1 -1 1 1 1 1 3 10 10 10
23
1 10
5 10
0
Output
1
4
3
3.2 NKLINEUP - Xếp hàng
Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn xếp
hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho
một số con bò. Để đơn giản, bác John se chọn ra một đoạn liên tiếp các con bò để
19
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bị phải khơng q
chênh lệch về chiều cao.
Bác John đã chuẩn bị một danh sách gồm Q (1 ≤ Q ≤ 200000) đoạn các con bò và
chiều cao của chúng (trong phạm vi [1, 1000000]). Với mỗi đoạn, bác John muốn
xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác
John thực hiện cơng việc này!
• Dịng đầu tiên chứa 2 số ngun N và Q.
• Dịng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của
con bị thứ i.
• Dịng thứ i trong số Q trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤
N), cho biết đoạn các con bò từ A đến B.
Input
63
1
7
3
4
2
5
15
46
22
Output
6
3
0
3.3 LITES - Bật đèn
Bác John giữ cho đàn bị thơng minh bằng cách để chúng chơi các đồ chơi
phát triển trí tuệ. Một trong các trò chơi là các ngọn đèn trong chuồng. Mỗi trong
số N (2 <= N <= 100,000) con bị được đánh số từ 1..N có treo một ngọn đèn màu.
Vào đầu buổi tối, tất cả đèn đều tắt. Đàn bị điều khiển các ngọn đèn bằng N cơng
tắc; bấm công tắc i đổi trạng thái của đèn i từ tắt sang bật hoặc ngược lại.
20
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
Đàn bị đọc và thực thi một danh sách gồm M (1 <= M <= 100,000) thao tác mô tả
bởi một trong hai số nguyên (0 <= thao tác <= 1).
Thao tác thứ nhất (mô tả bởi số 0) theo sau bởi hai số nguyên S_i và E_i (1 <= S_i
<= E_i <= N) cho biết công tắc đầu và công tắc cuối. Đàn bị se bấm mỗi cơng tắc
từ S_i đến E_i đúng một lần.
Thao tác thứ hai (mô tả bởi số 1) u cầu đàn bị đến xem có bao nhiêu ngọn đèn
giữa S_i và E_i (1 <= S_i <= E_i <= N) đang bật. Hãy giúp bác John đảm bảo rằng
đàn bò trả lời đúng bằng cách xử lý danh sách và trả về các kết quả đúng.
Dữ liệu
• Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: N và M
• Dịng 2..M+1: Mỗi dịng chứa một thao tác với ba số nguyên cách nhau bởi
khoảng trắng: thao tác, S_i, và E_i
Input
45
012
024
123
024
114
Output
1
2
KẾT LUẬN
1.Kết quả đạt được
Khi giải các bài tập bằng cây phân đoạn giúp em đánh giá, phân tích bài tốn
và hình thành tư duy theo cơng thức.
Đặc biệt quá trình thực hiện đồ án cơ sở giúp em làm quen với việc trình bày hồn
chỉnh một thuật toán cũng như đồ án tin học.
21
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
2. Hạn chế
Trong đồ án cơ sở ngành tìm hiểu một phương pháp mới nên bản thân chỉ
tiếp cận QHĐ ở mức độ đơn giản. Các bài tập được giải quyết để tìm ra lời giải và
khơng đặt ra vấn đề tối ưu bài toán với cấu trúc dữ liệu tốt hơn.
Bên cạch các bài đã giải được còn khá nhiều bài toán chưa giải quyết.
Tài liệu tham khảo
1.
2.
3.
4.
Tài liệu chia sẽ của thầy Phạm Anh Phương
Chuyên đề cấu trúc dữ liệu đặc biệt – Nguyễn Minh Hiếu
Website o
Website
22
Tìm hiểu cây phân đoạn
GVHD: TS. Phạm Anh Phương
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
23
