CHUYÊN ĐỀ: CẤU TRÚC DỮ LIỆU NÂNG CAO
Đặng Tuấn Thành
Trường THPT Chuyên Nguyễn Tất Thành, tỉnh Yên Bái
Interval Tree là công cụ rất hữu dụng được sử dụng nhiều trong các bài toán trên dãy
số, hoặc được quy về các bài toán xử lí trên dãy số, đặc biệt là các bài toán có nhiều
công việc cần xử lí và nhiều truy vấn xen kẽ nhau.
Phần lí thuyết về Interval Tree đã được trình bày rất rõ ràng ở nhiều tài liệu do các
chuyên gia, đồng nghiệp dạy bồi dưỡng học sinh giỏi chia sẻ, nên tôi mạn phép
không đề cập tại đây.
Do năng lực có hạn nên tôi không viết hoặc nghĩ ra những bài tập mới mà có sử dụng
Interval Tree để giải được. Vì thế, trong chuyên đề này thực chất là các bài tập tôi
sưu tầm, biên tập thành tập tài liệu để phục vụ trong công tác giảng dạy bồi dưỡng
HSG môn Tin học. Ở đây, tôi trích dẫn các bài tập nguồn từ SPOJ, Codeforce và
nhiều nguồn khác. Với mỗi bài tập tôi đề cập đến ba vấn đề:
• Tóm tắt đề bài rõ ràng
• Thuật toán tốt
• Code demo (nếu có).
Khi áp dụng tài liệu này vào giảng dạy, tôi thường bỏ phần “code demo” để không
“làm hỏng học sinh”, chỉ phát đề cho học sinh.Với mỗi bài tập, sau khi học sinh
nghiên cứu và đề xuất ý tưởng (hoặc code nộp mà chưa AC), tôi dẫn dắt, đưa ra giải
thuật của bài toán đó để học sinh “ngấm” bài toán hơn. Dần dần học sinh nắm được
tư tưởng Interval Tree và ứng dụng linh động vào các bài toán khác.
Tôi cũng xin trích dẫn các tài liệu tôi tham khảo để biên tập thành chuyên đề này:
•
•
•
•
•

/> /> /> /> />
tap-interval-tree/

• Quyển: Một số vấn đề chú ý môn Tin học – Nhóm tác giả của Đại học Vinh

1


Ứng dụng Interval Tree để giải các bài toán sau:
Bài 1. Phần tử thứ K />Cho dãy số A có N phần tử nguyên phân biệt.
Cho Q truy vấn, mỗi truy vấn có dạng: L R K
Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử A L,
AL+1, …, AR theo thứ tự tăng dần.
Giới hạn:
1 ≤ N, Q ≤ 105
|Ai| ≤ 109 với 1 ≤ i ≤ N
1≤L≤R≤N
1 ≤ K ≤ R-L+1
Input:
-

Dòng đầu tiên chứa số N.

-

Dòng tiếp theo chứa N số A1, A2, …, AN.

-

Dòng tiếp theo chứa số Q.

-


Q dòng tiếp theo, mỗi dòng chứa 3 số L, R, K.

Output:
Q dòng, mỗi dòng chứa câu trả lời cho một truy vấn theo thứ tự nhập vào.
Ví dụ:
Input
7

Output
2

2154368

6

4

4

122

3

374
462
Thời gian chạy:

551
1s-3s


2


THUẬT TOÁN :

Dùng Segment Tree với mỗi nút lưu lại dãy con từ l->r đã được sort. Dùng vector cho
mỗi nút để giảm bộ nhớ: mỗi nút sẽ xuất hiện logN lần trên cây, do đó bộ nhớ là
NlogN. Có thể tạo cây trong O(NlogN), mỗi lần hợp hai nút con lại ta trộn hai đoạn
con trong O(n+m) với n, m là kích thước của hai đoạn con.
Với mỗi truy vấn ta làm như sau: Xét các giá trị (gọi là res) có trong dãy bằng cách
chặt nhị phân, (nút 1 thực chất đã sort dãy tăng dần nên có thể chặt nhị phân trên nút
1), đếm xem trong đoạn l..r có bao nhiêu phần tử nhỏ hơn nó, nếu nhỏ hơn k tức là
phải tìm số lớn hơn nữa và tương tự. Với mỗi lần truy vấn l..r thì ta lại chặt nhị phân
những nút nằm trong đoạn l..r để tìm phần tử lớn nhất ≤ res đồng thời kiểm tra xem
res có mặt cũng như đếm số lượng phần tử nhỏ hơn res (Chú ý là các phần tử là phân
biệt). Điều kiện để res là nghiệm chính là cnt == k-1 (cnt là số lượng số < res) và tìm
thấy res trong đoạn l..r.
Code demo: />#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int64_t ll;
typedef pair<int,int> ii;
#define EL printf("\n")
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef vector<int> data;
const int N = 100100;
int

n, q, a[N], L, R, k, res, cnt, f;
data
t[4*N], nil;
data combine(data u, data v)
{
data ans = nil;
int i = 0, j = 0;
while (i < u.size() and j < v.size())
{
if (u[i] < v[j]) ans.pb(u[i++]);
else ans.pb(v[j++]);
}
while (i < u.size()) ans.pb(u[i++]);

void get(int node, int l, int r)
{
if (r < L or R < l) return ;
if (L ≤ l and r ≤ R) {
int i = 0, j = t[node].size()-1, pos
= -1;
while (i ≤ j) {
int mid = (i+j)/2;
if (t[node][mid] ≤ res) {
pos = mid;
i = mid+1;
}
else j = mid-1;
}
if (pos == -1) return ;
if (t[node][pos] == res) f = true;

cnt += pos + 1;
if (t[node][pos] == res) cnt--;
return ;
}
int mid = (l+r)/2;
get(node*2,l,mid);
get(node*2+1,mid+1,r);
}

3


while (j < v.size()) ans.pb(v[j++]);
return ans;
}
void build(int k, int l, int r)
{
if (l == r) {
t[k].pb(a[l]);
return ;
}
int mid = (l+r)/2;
build(k*2, l, mid);
build(k*2+1, mid+1, r);
t[k] = combine(t[k*2], t[k*2+1]);
}

int main()
{
//freopen("YPKTH.INP","r",stdin);

//freopen("YPKTH.OUT","w",stdout);
scanf("%d", &n);
for (int i=1;i≤n;i++) scanf("%d",
&a[i]);
build(1,1,n);
scanf("%d", &q);
while (q--) {
scanf("%d%d%d", &L,&R,&k);
int l = 0, r = t[1].size()-1;
while (l ≤ r) {
int mid = (l+r)/2;
res = t[1][mid];
cnt = 0;
f = 0;
get(1,1,n);
if (cnt == k-1 and f) {
printf("%d\n", res);
break;
}
if (cnt < k) l = mid+1; else r
= mid-1;
}
}
return 0;
}

Bài 2.Đoạn con có tổng lớn nhất />Cho dãy số a[1], a[2], ..., a[n] (|a[i]| ≤ 15000, n ≤ 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x ≤ i ≤ j ≤y }.
Cho m câu hỏi dạng x, y (1 ≤ x ≤ y ≤ n), (m ≤ 50000) -> hãy tính các q(x, y).
Input

- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
4


- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
12
Output:
2
Thời gian chạy:

Thuật toán: Sử dụng Segment Tree
Một nút lưu các giá trị :
sum : tổng đoạn
pre : tổng lớn nhất của đoạn tiền tố
suf : tổng lớn nhất của đoạn hậu tố
ans : tổng lớn nhất của đoạn
Công thức hợp hai nút trên cây như sau :
res.sum= l.sum+ r.sum;
res.pre= max(l.pre, l.sum+ r.pre);
res.suf= max(r.suf, r.sum+ l.suf);
5



res.ans= max(l.ans, r.ans, l.suf+ r.pre);
Code demo:
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <list>

data make_data (int x)
{
data res;
res.sum = x;
res.pre = res.suf = res.ans = x;
return res;
}

void make_tree(int k, int l, int r)
{
if (l == r) {
t[k] = make_data(a[l]);
return ;
}
int mid = (l+r)/2;
make_tree(k*2, l, mid);
make_tree(k*2+1, mid+1, r);

using namespace std;
typedef long long ll;
typedef int64_t ll;
typedef double real;
const int
const int
const ll
const real

base = 1000000007;
oo = INT_MAX;
ooo = LONG_LONG_MAX;
pi = acos(-1.0);

t[k] = combine(t[k*2], t[k*2+1]);
}
data query(int k, int l, int r, int L, int R)
{
if (l == L and r == R) return t[k];
int mid = (l+r)/2;

if (R ≤ mid)
return query(k*2, l, mid, L, R);

#define
openf
{freopen("INP.INP","r",stdin);freopen("OU
T.OUT","w",stdout);}
#define
closef
{fclose(stdin);fclose(stdout);}
#define readln
scanf("\n")
#define writeln printf("\n")

if (L > mid)
return query(k*2+1, mid+1, r, L, R);
return
combine (
query(k*2, l, mid, L, mid),
query(k*2+1, mid+1, r, mid+1, R)
);

//---------------------------------------------------/
/
}
struct data
{
int sum, pre, suf, ans;
};
const int maxn = 100000, maxt = 4*maxn;

int
n, a[maxn], m, L, R;
data
t[maxt];

int main()
{
//openf;
scanf("%d", &n);
for (int i=1;i≤n;i++) scanf("%d", &a[i]);

6


data combine (data l, data r)
make_tree(1,1,n);
{
data res;
scanf("%d", &m);
res.sum = l.sum + r.sum;
while (m--) {
res.pre = max(l.pre, l.sum + r.pre);
scanf("%d%d",&L,&R);
res.suf = max(r.suf, r.sum + l.suf);
printf("%d\n",query(1,1,n,L,R).ans);
res.ans = max( max(l.ans, r.ans), l.suf + }
r.pre);
return res;
//closef;
}

return 0;
}

Bài 3. Diện tích hình chữ nhật - />Trên mặt phẳng toạ độ người ta vẽ ra N hình chữ nhật. Hãy tính diện tích che phủ bởi
N hình chữ nhật này, biết rằng N hình chữ nhật này song song với 2 trục Ox và Oy .
Input
Dòng 1 : Số nguyên N ( 1 ≤ N ≤ 10000 ).
N dòng tiếp theo, mỗi dòng gồm 4 số nguyên x1, y1, x2, y2
tương ứng là toạ độ góc trái dưới và góc phải trên của hình
chữ nhật thứ i.( 0 ≤ x1 ≤ x2 ≤ 30000, 0 ≤ y1 ≤ y2 ≤ 30000 ).
Output
Gồm 1 dòng ghi ra diện tích phủ bởi N hình chữ nhật
Example
Input:
2
10 10 20 20
15 15 25 30
Output:
225
Thời gian chạy:

7


Thuật toán:
Sử dụng Segment Tree (IT).
Chuyển dữ liệu đề cho sang một dãy tọa độ x, mỗi x có lưu lại y1 và y2 tương ứng
hàng giới hạn dưới và trên, đồng thời lưu lại type là -1 hay 1 tương ứng là cạnh đóng
hay mở. Sau đó sort lại mảng này theo x.
Mục đích của cách xử lí trên là tại mỗi khoảng từ xi -> xi+1 xét trên dãy đã sort ta đi

tính phần diện tích được bao phủ bởi các y1 và y2. Lúc này ta dùng Segment Tree,
mỗi nút lưu lại cnt là số lượng đoạn phủ và len là tổng chiều dài.
Code demo: />#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long
typedef int64_t
typedef double

ll;
ll;
real;

//-------------------------------------//
struct Node {
int x, y1, y2, type;
};
struct Tree {

int len, cnt;
};
//-----------------------------------//
const int N = 30010;

void update(int k, int l, int r, int L, int R, int type)
{
if (r < L or R < l) return ;
if (L ≤ l and r ≤ R) {
t[k].cnt += type;
if (type == 1)
// them hcn nen bao phu
ca canh nay
t[k].len = (r-l+1); // chang han l = 5, r = 8
thi t[k].len = 4 do (5,6,7,8)
else {
// truong hop xoa thi phai
lay thong tin tu node con
if (t[k].cnt == 0)
t[k].len = t[k*2].len + t[k*2+1].len;
}
return ;
}
int mid = (l+r)/2;
update(k*2,l,mid,L,R,type);
update(k*2+1,mid+1,r,L,R,type);
if (t[k].cnt == 0)
t[k].len = t[k*2].len + t[k*2+1].len;
}
int main()

{
//freopen("INP.INP","r",stdin);
//freopen("OUT.OUT","w",stdout);
scanf("%d", &n);
for (int i=1;i≤n;i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
a[i].x = x1;

8


int
n, x0; // x0 la vi tri cuoi cung dang
xet
ll
res;
Node
a[N];
Tree
t[5*N]; // luu ve phuong dien do
dai, khong phai toa do (*)
//------------------------------------//

a[i+n].x = x2;
a[i].y1 = a[i+n].y1 = y1;
a[i].y2 = a[i+n].y2 = y2;
a[i].type = 1;
a[i+n].type = -1;
}

n *= 2;
sort(a+1,a+n+1,cmp);

bool cmp(const Node u, const Node v)
{
//for (int i=1;i≤n;i++)
return (u.x < v.x or (u.x == v.x and u.type
// printf("%d %d %d %d\n", a[i].x, a[i].y1,
< v.type));
a[i].y2, a[i].type);
}
for (int i=1;i≤n;i++) {
//cout << (a[i].x-x0)*(t[1].len) << endl;
res += (a[i].x - x0) * (t[1].len);
x0 = a[i].x;
update(1,0,N, a[i].y1, a[i].y2-1, a[i].type); //
a[i].y2-1 la do (*)
}
cout << res;
return 0;
}

Bài 4. />Cho danh sách N lập trình viên (1 ≤ N ≤ 300000), đánh số lần lượt từ 1 đến N. Mỗi
người đều tham gia cả hai giải thi đấu: Giải THPT và giải Mở rộng. Với mỗi lập trình
viên, bạn sẽ được cung cấp điểm số của giải Mở rộng Ai và điểm số của giải THPT
Hi (Các điểm số đều là số nguyên không âm và không vượt quá 100000). Lập trình
viên i được coi là giỏi hơn lập trình viên j khi và chỉ khi cả 2 điểm số của lập trình
viên i đều lớn hơn hoặc bằng điểm số tương ứng của lập trình viên j, trong đó có ít
nhất 1 điểm số phải lớn hơn. Hãy tính xem với mỗi lập trình viên i thì có bao nhiêu
lập trình viên mà i giỏi hơn.

Input
Dòng đầu tiên chứa số nguyên N.
N dòng tiếp theo, dòng thứ i+1 chứa 2 số nguyên Ai và Hi.
Output
9


Dòng i chứa số lượng lập trình viên mà lập trình viên i giỏi hơn.
Example
Input:
8
1798 1832
862 700
1075 1089
1568 1557
2575 1984
1033 950
1656 1649
1014 1473
Output:
6
0
2
4
7
1
5
1
Thuật toán:
Ở bài này, giới hạn của bài toán khá lớn (300000) nên nếu dùng N log N thì cũng còn

nguy hiểm. Chú ý giới hạn của số điểm là 0..100000 nên ta sẽ xử lí trên số điểm.
+ Tạo một danh sách các thông tin của từng người: struct(C++) ds gồm d1,d2 là
điểm lần 1 và 2, vt là vị trí ban đầu của nó. Mảng A sẽ lưu danh sách này.
+ Tạo một mảng res sẽ chứa mảng cần xuất ra khi đã thực hiện xong chương trình.
Cách tạo res là for i = 1 -> n rồi lưu res[a[i].vt] = giá trị tìm được của thằng a[i].vt (vị
trí ban đầu của nó). Sau đó xuất ra theo thứ tự trong res.
+ Tạo một cây IT là mảng t[k] lưu thông tin của nút k quản lí đoạn l..r (xét trên số
điểm) và một mảng f lưu nghiệm của bài toán, tức là f[i] là số lượng những thằng tồi
hơn thằng i sau khi đã sort lại.
10


+ Tạo thêm biến m lưu số điểm d2 lớn nhất vì theo như tài liệu d1 ta đã sort lại rồi thì
không cần quan tâm điểm lớn hay nhỏ.
+ Sau khi nhập dữ liệu thì sort lại dãy.
+ Tạo biến q là vị trí đang duyệt trên dãy a ( từ 1 -> n, lần lượt xét các đoạn có cùng
d1). Khi q > n thì xuất nghiệm ra, halt luôn. trước hết q = 0.
+ Tạo biến L và R lưu đoạn xét nói trên. Khi đó ban đầu L = q và R = q. lần lượt tăng
R lên đến khi d1 thay đổi. Xong thì xét đoạn L..R mới tìm được.
+Khởi tạo f[L] = 0. Tạo f.
+ Sau đó lấy giá trị cho f trên cây t (nhớ là xét trên số điểm từ 0..m, đoạn ban đầu
findans) : điểm đang xét là x. Ta sẽ tìm những đoạn mà r ≤ x để lấy ans còn những
đoạn nào mà x < l ( điểm thấp hơn ) thì ta bỏ qua. Trường hợp còn lại thì chia ra 2
đoạn mà làm như các bài IT cơ bản.
+ Lấy giá trị xong thì cập nhật lại cây t: bỏ qua những đoạn x không thuộc, tăng số
lượng nút này lên, nếu l = r thì thôi. chia hai đoạn để it.
+ q = R.
+ Duyệt
Code demo:
#include <iostream>

#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

bool compare(const ds u, const ds v)
{
if (u.d1 < v.d1) return true;
if (u.d1 == v.d1 and u.d2 < v.d2) return true;
return false;
}

using namespace std;

int main(){
scanf("%d",&n);
struct ds {
for (int i=1;i≤n;i++) {
int d1,d2,vt;
scanf("%d%d",&a[i].d1,&a[i].d2);
};
a[i].vt = i;
m = max(m,a[i].d2);
const int
maxn = 300010, maxt =
}

11



maxn*4 + 1;
int
n,m,q,L,R;
ds
a[maxn];
int
t[maxt],f[maxn],res[maxn];
void findans(int k, int l, int r, int x, int &ans)
{
if (x < l) return;
if (r ≤ x) {
ans += t[k];
return;
}
int m = (l+r)/2;
findans(k*2,l,m,x,ans);
+;
findans(k*2+1,m+1,r,x,ans);
}
void update(int k, int l, int r, int x)
{
if (x < l or r < x) return;
t[k]++;
if (l == r) return;
int m = (l+r)/2;
update(k*2,l,m,x);
update(k*2+1,m+1,r,x);
}


//-------------------------------------//
sort(a+1,a+n+1,compare);
q = 0;
while (1 == 1) {
q++;
if (q > n) {
for (int i=1;i≤n;i++) res[a[i].vt] = f[i];
for (int i=1;i≤n;i++) printf("%d\n",res[i]);
return 0;
}
L = q;
R = q;
while (R < n and a[R].d1 == a[R+1].d1) R+
f[L] = 0;
for (int i=L+1;i≤R;i++)
if (a[i].d2 ≤ a[i-1].d2) f[i] = f[i-1];
else f[i] = i - L;
for (int i=L;i≤R;i++) {
int ans = 0;
findans(1,0,m,a[i].d2,ans);
f[i] += ans;
}
for (int i=L;i≤R;i++) update(1,0,m,a[i].d2);
q = R;
}
return 0;

}

Bài 5. />Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị
trí v lên k đơn vị.
Cho q câu hỏi, mỗi câu có dạng (u, v): Cho biết phần tử có giá trị lớn nhất thuộc đoạn
[u, v]
Input
– n: số phần tử của dãy (n ≤ 50000).
– m: số lượng biến đổi và câu hỏi (m ≤ 100000).
12


+) biến đổi có dạng: 0 x y value
+) câu hỏi có dạng : 1 x y.
Output
Ghi ra trả lời cho lần lượt từng câu hỏi.
Example
Input:
63
0133
0464
116
Output:
4
Thuật toán:
Để làm bài này, ta gọi F[k] là giá trị lớn nhất trong đoạn mà nút k quản lí, trong lúc
cập nhật, muốn đảm bảo thủ tục này không vượt quá log(n) thì khi đi đến 1 nút mà
nằm gọn trong đoạn x..y thì takhông được đi vào các nút con của nó nữa(nếu không
sẽ đi đến tất cả các đoạn có trong đoạn x..yvà độ phức tạp tỷ lệ với n).
Nếu như vậy, ta cần có 1 mảng phụ T để lưu lại giá trị cần tăng lên chotất cả các phần
tử của đoạn này, khi ta truy vấn đến 1 nút k đồng thời ta tăng T[k] lên cho T[k*2],
T[k*2+1] và F[k]. (do T[k] là giá trị cần tăng lên cho tất cả những phần tử của đoạn

nút k quản lí,nên các nút con của nó cũng phải tăng lên T[k]).
Sau khi đã cập nhật cho mảng F và các nút con, tagán lại T[k]=0 để tránh trường hợp
cộng lại nhiều lần. Nếu đã đến đoạn nằm gọn trong đoạn x..ythì ta tăng mỗi biến F[k],
T[k*2], T[k*2+1] lên v. Khi muốn lấy kết quả, ta vẫn làm như bàiQMAX, nhưng đến
13


mỗi nút con, ta vẫn cần thực hiện tăng giá trị T[k] cho T[k*2], T[k*2+1] vàF[k] để
lấy được kết quả. Tức là khi đến được 1 nút nào đó (trong bất kì thao tác nào, cập
nhật hay lấy kết quả) thì đều thực hiện như vậy. Điều này đảm bảo là ta có thể lấy
được giá trị chính xác,đây là kiểu cây IT có thông tin truyền từ nút cha xuống nút
con. Các bạn có thể tham khảo chươngtrình để thấy rõ hơn.
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stdlib.h>
usingnamespace std;

void solve0(){
scanf("%li%li%li",&L,&R,&v);
update(1,1,n);
}
void solve1(){
scanf("%li%li",&L,&R);
res = 0;
findres(1,1,n);

printf("%li\n",res);
}

const long maxn = 50000 + 100;
long
int main()
n,m,L,R,loai,v,a[maxn],f[8*maxn],t[8*maxn],res {
;
scanf("%li%li",&n,&m);
/**
for(long i=1;i≤m;i++){
t[k] la max cua doan nut k quan li
scanf("%li",&loai);
f[k] la mang phu luu phan can tang len cua
if(loai == 0) solve0();
doan nut k
else solve1();
quan li
}
**/
return0;
void update(long k,long l,long r){
}
t[k] += f[k];
f[k*2] += f[k];
f[k*2+1] += f[k];
f[k] = 0;
if(r < L or R < l)return;
if(L ≤ l and r ≤ R){
t[k] += v;

f[k*2] += v;
f[k*2+1] += v;
return;
}
long m = (l+r)/2;
update(k*2,l,m);
update(k*2+1,m+1,r);
t[k] = max(t[k*2],t[k*2+1]);
}
void findres(long k,long l,long r){
t[k] += f[k];
f[k*2] += f[k];
f[k*2+1] += f[k];

14


f[k] = 0;
if(r < L or R < l)return;
if(L ≤ l and r ≤ R){
res = max(res,t[k]);
return;
}
long m = (l+r)/2;
findres(k*2,l,m);
findres(k*2+1,m+1,r);
}

Bài 6. />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 sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò
chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá 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ữ liệu
•

Dòng đầu tiên chứa 2 số nguyên 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.

Kết quả
Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữa con bò thấp
nhất và cao nhất thuộc đoạn tương ứng.
Ví dụ
Dữ liệu:
63
1
7
3

4
2
15


5
15
46
22
Kết qủa
6
3
0
Thuật toán:
Đây là 1 bài toán xử lí trên dãy số và cần truy cập đến những đoạn A..B bất kì trong
dãy, vì vậyinterval tree là 1 trong những lựa chọn tốt. Bài này chúng ta có 1 điều may
mắn là không cầnphải cập nhật lại chiều cao của các con bò, vì vậy thông tin trong
cây interval tree là cố định và tasẽ tạo cây interval tree dựa trên mảng chiều cao của
các con bò.
Mỗi đoạn thì ta cần in ra chênhlệch độ cao con bò cao nhất và con bò thấp nhất, vì
vậy chúng ta cần tìm được giá trị lớn nhất vàgiá trị nhỏ nhất trong các phần tử từ A
đến B. Ta có thể dùng 1 cây interval tree với mỗi nút lưu 2thông tin, giá trị lớn nhất
và giá trị nhỏ nhất trong đoạn mà nó biểu diễn, cũng có thể dùng 2 cây interval tree, 1
cây dùng để lưu giá trị lớn nhất, cây còn lại là giá trị nhỏ nhất. Ở đây ta gọi 2 câynày
là maxt và mint.
Khi muốn tìm kết quả thì dựa vào mảng Maxt để tìm GTLN trên đoạn A..B, dùng
mảng Mint đểtìm GTNN trên đoạn A..B, việc này làm tương tự như trong ví dụ của
bài viết giới thiệu về Intervaltree phía trên. Chú ý là khi tìm max hay tìm min ta đều
phải đi đến những nút giống nhau (do điđến những nút nào thì chỉ phụ thuộc A và B)
nên mỗi lần tìm chỉ cần gọi chung 1 thủ tục.

#include <iostream>
#include <cmath>
int main()
#include <algorithm>
{
#include <cstdio>
scanf("%li%li",&n,&q);
#include <stdlib.h>
for (long i=1;i≤n;i++) scanf("%li",&a[i]);
using namespace std;
update(1,1,n);
const long maxn = 50000+100, maxh =
for (long Q=1;Q≤q;Q++) {
1000000;
scanf("%li%li",&L,&R);

16


long
n,q,L,R,a[maxn],tmax[4*maxn],tmin[4*maxn],h
max,hmin;
void update(long k,long l,long r) {
if (l == r) tmin[k] = tmax[k] = a[l];
else {
long m = (l+r)/2;
update(k*2,l,m);
update(k*2+1,m+1,r);
tmax[k] = max(tmax[k*2],tmax[k*2+1]);
tmin[k] = min(tmin[k*2],tmin[k*2+1]);

}
}
void findres(long k,long l,long r) {
if (not(r < L or R < l)) {
if (L ≤ l and r ≤ R) {
hmax = max(hmax,tmax[k]);
hmin = min(hmin,tmin[k]);
}
else {
long m = (l+r)/2;
findres(k*2,l,m);
findres(k*2+1,m+1,r);
}
}
}

hmax = 1;
hmin = maxh;
findres(1,1,n);
printf("%li\n",hmax-hmin);
}
return 0;
}

Bài 7. />Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.
Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị
trí v lên k đơn vị.
Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn
[u, v].
Giới hạn

•

n, m, q ≤ 50000

•

k>0

•

Giá trị của một phần tử luôn không vượt quá 231-1

Input
•

Dòng 1: n, m

•

m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi
17


•

Dòng thứ m+2: p

•

p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi


Output
•

Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.

Example
Input:
62
132
463
1
34
Output:
3
Thuật toán:
Bài này thì ta có m phép biến đổi tăng dãy trước rồi mới yêu cầu tìm giá trị lớn nhất
trong các đoạnchứ không phải xen kẽ nhau, vì vậy ta sẽ tìm cách xây dựng dãy số sau
m phép biến đổi. Khi cóđược mảng giá trị sau m phép biến đổi, công việc còn lại của
ta là tạo 1 cây interval tree với mỗinút lưu giá trị lớn nhất của đoạn mà nó quản lí
trong khi các phần tử của mảng đã xác định, với mốitruy vấn tìm GTLN thì ta có thể
làm không mấy khó khăn.
Vấn đề bây giờ là xây dựng dãy số sau m phép biến đổi.
Ta có thể sử dụng 1 kĩ thuật đơn giản những rất hiệu quả như sau.
Giả sử mảng ta cần có là mảng A[0..n+1], lúc đầu A[i]=0 với mọi i.
Mỗi yêu cầu u,v,k tức là tăng các phần tử từ vị trí u đến vị trí v lên k đơn vị, ta làm
như sau:A[u]:=A[u]+k;A[v+1]:=A[v+1]-k;
Sau khi đọc xong m phép biến đổi và làm như trên, cuối cùng là tính mảng A:
For i:=1 to n do
A[i]:=A[i]+A[i-1];

Các bạn có thể tự chứng minh tính đúng đắn hay có thể viết đoạn chương trình này ra
và kiểmnghiệm lại. Như vậy ta đã có thể giải quyết trọn vẹn bài toán.
18


#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <stdlib.h>
using namespace std;
const long maxn = 50000+100;
long
n,m,k,u,v,q,L,R,a[maxn],t[4*maxn],res;
void update(long k,long l,long r) {
if (l == r) t[k] = a[l];
else {
long m = (l+r)/2;
update(k*2,l,m);
update(k*2+1,m+1,r);
t[k] = max(t[k*2],t[k*2+1]);
}
}

void findres(long k,long l,long r) {
if (not(r < L or R < l)) {
if (L ≤ l and r ≤ R)
res = max(res,t[k]);
else {
long m = (l+r)/2;

findres(k*2,l,m);
findres(k*2+1,m+1,r);
}
}
}
int main()
{
scanf("%li%li",&n,&m);
for (long i=1;i≤m;i++) {
scanf("%li%li%li",&u,&v,&k);
a[u] += k;
a[v+1] -= k;
}
for (long i=1;i≤n;i++) a[i] += a[i-1];
update(1,1,n);
scanf("%li",&q);
for (long Q=1;Q≤q;Q++) {
scanf("%li%li",&L,&R);
res = 0;
findres(1,1,n);
printf("%li\n",res);
}
return 0;}

Bài 8.Dãy ngoặc />Khái niệm dãy ngoặc đúng được định nghĩa dưới dạng đệ quy như sau:
1. () là dãy ngoặc đúng
2. C là dãy ngoặc đúng nếu C = (A) hay C = AB với A, B là các dãy ngoặc đúng.
Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(
Cho trước một dãy ngoặc bất kỳ gồm n dấu ngoặc được đánh số từ 1 đến n. Có m câu

hỏi, mỗi câu gồm hai số nguyên 1 ≤ p ≤ r ≤ n, yêu cầu xác định xem dãy ngoặc
con từ vị trí p đến vị trí r có phải là dãy ngoặc đúng hay không. Hãy cho biết kết quả
của m câu hỏi trên.
Dữ liệu nhập:
– Dòng đầu tiên là hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 105)
19


– Dòng thứ hai là dãy ngoặc ban đầu gồm n dấu ngoặc ‘(‘ hay ‘)’.
– Trong m dòng tiếp theo, tại dòng thứ i là hai số p i và ri của câu hỏi thứ i tương ứng,
hai số cách nhau một khoảng trắng. (1 ≤ pi ≤ ri ≤ n).
Dữ liệu xuất:
– Gồm m dòng ứng với m câu hỏi, nếu dãy ngoặc con tương ứng là dãy ngoặc đúng,
in ra YES, nếu dãy ngoặc con tương ứng là không phải dãy ngoặc đúng, in ra NO.
Ví dụ
input

•

85
(((())))
14
36
48
45
27
output
NO
YES
NO

YES
YES
Thuật toán:
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, bb[400001], cc[400001];
char ch;
void update(int k, int x, int y, int d, int c, int v)
{
if (cif (d≤x && y≤c) bb[k]+=v, cc[k]+=v;
else
{
int m = (x+y)/2;

bool check(int u, int v)
{
if ((v-u+1) & 1) return 0;
int y = (u == 1 ? 0 : get(1, 1, n, u-1, u-1));
int z = get(1, 1, n, v, v);
if (y != z) return 0;
else return (get(1, 1, n, u, v-1) >= z);
}
main()
{

20


update(2*k, x, m, d, c, v);

update(2*k+1, m+1, y, d, c, v);
bb[k] = min(bb[2*k],bb[2*k+1]) + cc[k];
}
}
int get(int k, int x, int y, int d, int c)
{
if (cif (d≤x && y≤c) return bb[k];
else
{
int m=(x+y)/2;
return min(get(2*k, x, m, d, c), get(2*k+1,
m+1, y, d, c)) + cc[k];
}
}

scanf("%d %d\n", &n, &m);
for (int i=1; i≤n; i++)
{
scanf("%c", &ch);
x += (ch == '(') ? 1 : -1;
update(1, 1, n, i, i, x);
}
while (m--)
{
scanf("%d %d\n", &x, &y);
printf("%s\n", check(x,y) ? "YES" : "NO");
}
}

Bài 9. Búp bê Nga
Búp bê Nga(Búp bê lồng nhau, Búp bê làm tổ, …) là một loại búp bê đặc trưng của
Nga. Thật ra đó là một bộ gồm những búp bê rỗng ruột có kích thước từ lớn đến nhỏ.
Con búp bê nhỏ nhất sẽ được chứa đựng trong lòng con búp bê lớn hơn nó một chút,
đến lượt mình con búp bê lớn được chứa trong một con búp bê khác lớn hơn, và cứ
thế cho đến con lớn nhất sẽ chứa tất cả những con búp bê còn lại trong bộ.
Đầu tiên yenthanh132 sắp xếp N con búp bê của anh ta từ trái sang phải theo một thứ
tự bất kì, con thứ i có kích thước ai (1 ≤ ai ≤ M). Sau đó anh ta yêu cầu bạn tạo
khoảng trống ở đầu mút trái, để làm được điều đó, bạn cần xếp những con búp bê có
kích thước nhỏ hơn ở bên trái đặt vào những con búp bê có kích thước lớn hơn bên
phải, tuy nhiên mỗi con búp bê lớn hơn chỉ chứa đúng 1 con búp bê nhỏ hơn nó. Bạn
chỉ được quyền dùng 3 thao tác: Lấy một con búp bê ở bên trái lên, di chuyển nó sang
phải và đặt vào bên trong một con búp bê lớn hơn. Bạn cần tìm cách sắp xếp sao cho
khoảng trống ở đầu mút trái là lớn nhất.
Nói cách khác, yenthanh132 yêu cầu bạn tìm một số nguyên K lớn nhất (1 ≤ K ≤ N/2)
sao cho K con búp bê trái nhất có để đặt vào bên trong K con búp bê ngay sau đó (từ
k+1..k*2), mỗi con búp bê chỉ chứa đúng 1 con búp bê, theo một thứ tự nào đó. Lưu ý
con búp bê i có thể đặt vào bên trong con búp bê j nếu (ai < aj).
Dữ liệu vào:
21


Dòng đầu tiên có 2 số N, M lần lượt là số lượng con búp bê của yenthanh132 và kích
thước giới hạn của N con búp bê đó. N luôn là số chẵn.
Dòng thứ 2 chứa N số ai, là kích thước của N con búp bê từ trái sang phải. (1
≤ ai ≤ M).
Dữ liệu ra:
Xuất ra số K theo yêu cầu của bài. Nếu không có kết quả (không có cách sắp nào để
tạo khoảng trống ở đầu mút trái ) thì xuất ra -1.
Giới hạn test:

20% test đầu có (1 ≤ N ≤ 100; 1 ≤ M ≤ 1000).
20% test tiếp theo có (1 ≤ N ≤ 10000; 1 ≤ M ≤ 1000).
60% test còn lại có (1 ≤ N ≤ 105; 1 ≤ M ≤ 105).
Ví dụ:
Input:
10

5

2142324523
Output:
4
Giải thích:
Ta có thể đặt 4 con búp bê bên trái vào trong 4 con búp bê bên cạnh theo thứ tự như
sau:1 đặt vào 5, 2 đặt vào 6, 3 đặt vào 8, 4 đặt vào 7.
Input 2:
45
2211
Output 2:
-1
Thuật toán:Nguồn Lê Yên Thanh - o
Cách làm O(n*m):

22


– Đầu tiên ta cho biến k chạy từ n/2 về 1. Với mỗi giá trị của k, ta gọi l[i] là số lượng
các phần tử có giá trị bằng i trong đoạn từ 1..k; r[i] là số lượng các phần tử bằng i
trong đoạn từ k+1..k*2; với i từ 1 đến m.
– Ta định nghĩa thêm một mảng d[1..m] như sau: d[m]=-l[m]; d[i] = d[i+1] + r[i+1] –

l[i] (với i từ 1 đến m-1).
– Ta có thể nhận thấy một điều là tồn tại một cách sắp k con búp bê ở đoạn từ 1..k
vào k con búp bê ở đoạn k+1..k*2 khi và chỉ khi d[i]>=0 với mọi i từ 1 đến m.
– Như vậy, với mỗi giá trị của k, ta sẽ xây dựng lại các giá trị của mảng l,r,d và thực
hiện kiểm tra điều kiện d[i] ≥ 0 với mọi i từ 1 đến m.
– Cách làm này sẽ ăn được 40% số điểm.
Cách làm O(n*log(m))
– Ta có thể thấy trong quá trình duyệt k từ n/2 về 1. Mỗi lần giảm giá trị k đi 1 đơn vị
thì ta sẽ giảm một phần tử trong mảng l[1..m] 1 đơn vị, tăng 1 phần tử và giảm 2 phần
tử trong mảng r[1..m] 1 đơn vị.
– Ta có thể thấy rằng giá trị của phần tử d[i] = r[m] + r[m-1] + … + r[i+1] – l[m] –
l[m-1] – … – l[i]. Như vậy, một thao tác tăng/giảm phần tử r[i] 1 đơn vị sẽ tương ứng
với thao tác tăng/giảm các phần tử trong đoạn d[1..i-1] 1 đơn vị; một thao tác
tăng/giảm phần tử l[i] 1 đơn vị sẽ tương ứng với thao tác tăng/giảm các phần tử trong
đoạn d[1..i] 1 đơn vị.
– Như vậy ta có thể sử dụng một Interval Tree để thực hiện 2 thao tác: Tăng/giảm giá
trị của 1 đoạn phần tử trong log(m); Lấy giá trị của phần tử nhỏ nhất trong O(1). Với
mỗi lần duyệt của biến k, ta sẽ thao tác cập nhật trên cây Interval Tree này và nếu giá
trị của phần tử nhỏ nhất trong mảng d[1..m] là một số không âm thì k chính là kết quả
cần tìm.
– Cách làm này sẽ đạt được toàn bộ số điểm.
Bài 10. Bật đèn(LITES)
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.
23


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.

Đà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ò sẽ 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) yê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
Kết quả:
* Dòng 1..số truy vấn: Với mỗi truy vấn, in ra kết quả là một số nguyên trên một
dòng.
Ví dụ:
Dữ liệu:
45
012
024
123
024
114
Kết quả:
1
2
Thuật toán:
24

Ta có thể sử dụng INTERVAL TREE để làm như sau:Bài này có tư tưởng
khá giống với bài QMAX2, thông tin được truyền từ nút cha xuống nút
conbất cứ khi nào có thể. Ta có 1 mảng B kiểu logic, B[i]=true nghĩa
là những đèn trong đoạn mà nútthứ i quản lí cần thay đổi trạng thái.
Khi đến 1 nút, nếu b[i]=true thì cần thay đổi trạng thái củaB[i*2] và
B[i*2+1] đồng thời gán lại B[i]=false (đã thực hiện thay đổi rồi thì phải
gán lại false),nếu gọi mảng sl[i] là số lượng đèn đang bật trong đoạn do
nút i quản lí thì nếu gặp b[i]=true phảitiến hành sửa sl[i], sl[i] hiện tại
là giá trị của số đèn đang tắt( do khi thay đổi trạng thái thì bậtchuyển
thành tắt). Vậy chỉ cần 1 phép trừ là có thể tính được số lượng đèn đang
bật trong đoạn.
Các công việc này cần làm ở đầu ở cả 2 thủ tục cập nhật và lấy kết quả.
Khi thực hiện thao tác cập nhật kết quả cho đoạn x..y thì nếu gặp
những đoạn nằm gọn trong x..ythì ta lại thực hiện thay đổi trạng thái
như trên. Phần lấy kết quả thì không khó, các bạn chỉ cần nhớlà trong
thủ tục lấy kết quả cũng cần thực hiện truyền thông tin từ nút cha cho
nút con( bất cứ khinào có thể).
BÀI TẬP ĐỀ XUẤT GIẢI BẰNG INTERVAL TREE
Bài 11. A Marble Game(MARBLE)
Trong những ngày hè rảnh rỗi, ktuan thường chơi bắn bi trên một bảng hình vuông
gồm NxN ô vuông nhỏ. Trò chơi được thực hiện như sau:
- Ban đầu, ktuan đặt K vật cản vào K ô vuông của bảng.
- Sau đó, ktuan thực hiện lần lượt Q lượt chơi. Ở lượt chơi thứ i, ktuan lần lượt bắn
Di viên bi từ ngoài bảng vào một trong 4 đường biên của bảng. Kích thước của mỗi
viên bi đúng bằng kích thước của một ô vuông nhỏ. Viên bi sẽ đi qua các ô thuộc
cùng một hàng / cột cho đến khi đi ra ngoài bảng hoặc gặp một vật cản hay viên bi
khác. Nếu có vật cản hay viên bi khác ở ngay ô đầu tiên thì viên bi đó không được
đưa vào bảng.
- Ở mỗi lượt bắn, ktuan ghi lại tổng số ô mà các viên bi đã đi qua.
25