# CHUYÊN ĐỀ: CÁC BÀI TOÁN TRUY VẤN TRÊN ĐOẠN
:::info
Trong chuyên đề này, ta sẽ đề cập đến các bài toán thực hiện truy vấn trên đoạn. Với dữ liệu gốc là một mảng gồm $N$ phần từ và ta cần thực hiện đến $Q$ các truy vấn khác nhau. Tuỳ theo yêu cầu của các bài toán đưa ra, song, các truy vấn sẽ được chia thành 2 dạng chính:
- Dạng **đọc**: Yêu cầu đếm/tính tổng/tìm min-max/... của các phần tử trong một đoạn $[L; R]$
- Dạng **ghi**: Yêu cầu xoá/chèn/thay đổi phần tử tại một vị trí (hoặc một số vị trí) trên mảng.
:::
:::success
:warning: Đối với đa số các bài toán trong chủ đề này, phương pháp dễ tiếp cận nhất vẫn là thực thi lại bài toán nhiều lần. Tuy nhiên, độ phức tạp của các thuật toán cơ bản như vậy thường rất lớn và các phương pháp đơn giản đó sẽ không thể giúp thí sinh lấy trọn số điểm của câu hỏi (thường không thể lấy qua khỏi 50% số điểm). Do đó, tôi sẽ không đề cập đến phương pháp này trong chuyên đề này mà chỉ tập trung khai thác vào các cấu trúc dữ liệu và thuật toán có thể giúp thí sinh lấy được (gần) tối đa số điểm của câu hỏi.
:::
## :bangbang: Chủ đề 1: Chia căn (Sqrt Decomposition)
:::warning
- Ta được yêu cầu thực hiện $Q$ câu truy vấn tìm tổng các phần tử trong đoạn từ $[L; R]$.
- **Không** có truy vấn dạng ghi.
- Đối với bài toán có truy vấn dạng ghi (cụ thể là cập nhật một hoặc một số phần tử), các thuật toán dưới đây không còn hiệu quả cao nữa. Do đó, ta nên dùng một cấu trúc dữ liệu khác.
:::
### :pencil2: Mức cơ bản
:::success
Ý tưởng giải bài toán này là chia $N$ phần tử ra thành $s = \lceil \sqrt N \rceil$ blocks khác nhau. Do đó, mỗi block sẽ chứa tối đa $s$ phần tử.
- Ta tính trước tổng của các block, được mảng $b$ ($s$ phần tử)
- Khi đến một truy vấn trong đoạn $[L; R]$, bằng cách tính toán xem đoạn này bao phủ qua những block nào mà ta đã tính tổng trước đó, ta sẽ nhanh chóng tìm được tổng của đoạn này.
:::
:::success
:::spoiler :key: **Đáp án (Cách 1)**
```python=
import math
# Mảng
a = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75]
# q này đã được chuyển đổi sẵn về 0-based index
q = [(1, 3), (2, 5), (8, 12), (1, 10), (4, 14), (6, 9)]
# Tính toán mảng b
n = len(a)
s = int(math.sqrt(n)) + 1
b = [0] * s
for i in range(n):
b[i // s] += a[i]
# Trả lời các truy vấn
for query in q:
l, r = query
kq = 0
i = l
while i <= r:
if i % s == 0 and i + s - 1 <= r:
# TH1: kết quả đã có sẵn trong b
kq += b[i // s]
i += s
else:
# TH2: 2 đầu
kq += a[i]
i += 1
print(kq)
```
:::
:::success
:::spoiler :key: **Đáp án (Cách 2)**
```python=
import math
# Mảng
a = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75]
# q này đã được chuyển đổi sẵn về 0-based index
q = [(1, 3), (2, 5), (8, 12), (1, 10), (4, 14), (6, 9)]
# Tính toán mảng b
n = len(a)
s = int(math.sqrt(n)) + 1
b = [0] * s
for i in range(n):
b[i // s] += a[i]
# Trả lời các truy vấn
for query in q:
l, r = query
_sum = 0
c_l = l // s
c_r = r // s
if c_l == c_r:
# TH1: cùng block
for i in range(l, r + 1):
_sum += a[i]
else:
# TH2: trải dài các block
for i in range(l, (c_l + 1) * s):
_sum += a[i]
for i in range(c_l + 1, c_r):
_sum += b[i]
for i in range(c_r * s, r + 1):
_sum += a[i]
print(_sum)
```
:::
### :pencil2: Mở rộng bài toán
:::info
Giả sử trong $Q$ sẽ có thêm loại truy vấn cập nhật phần tử ở vị trí có chỉ số là $i$. Theo đó, nếu phần tử $a[i]$ thay đổi thì ta cũng phải cập nhật phần tử $b[k]$ tương ứng (với $k = \lfloor \frac i s \rfloor$) theo công thức:
Cần lưu ý thêm, nếu bài toán là tìm min-max trên các đoạn, việc cập nhật lại $b$ có thể sẽ phải chạy lại vòng lặp trong block tương ứng đó.
:::
:::warning
Giả sử loại truy vấn cập nhật này tác động lên một số phần tử (ví dụ: cộng thêm một giá trị $x$ vào đoạn $[L; R]$). Lúc này ta sẽ có thể cập nhật lại mảng $b$ cho một số block ứng với đoạn $[L, R]$ được yêu cầu.
:::
### :pencil2: Thuật toán Mo's
:::info
Giả sử rằng không có truy vấn dạng ghi. Hãy tiếp cận bài toán với một hướng giải khác:
- Sắp xếp các truy vấn sao cho các truy vấn trên các block gần nhau nằm gần nhau.
- Tạo một biến $mo$ để lưu giá trị tính toán được trước đó và điều chỉnh lại khi đi đến các truy vấn tiếp theo.
:::
:::success
:::spoiler :key: **Đáp án Thuật toán Mo's**
```python=
import math
# Mảng
a = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75]
# q này đã được chuyển đổi sẵn về 0-based index
q = [(1, 3), (2, 5), (8, 12), (1, 10), (4, 14), (6, 9)]
# Thêm index cho mỗi q
q = [(i, x[0], x[1]) for i, x in enumerate(q)]
# Biến lưu trữ lại kết quả
mo = 0
def mo_s_algorithm(q):
global mo
kq = [0] * len(q)
s = int(math.sqrt(len(a))) + 1
# Sắp xếp các truy vấn
q.sort(key=lambda x: (x[1] // s, x[2]))
cur_l = 0
cur_r = -1
for i, (idx, l, r) in enumerate(q):
while cur_l > l:
cur_l -= 1
mo += a[cur_l]
while cur_r < r:
cur_r += 1
mo += a[cur_r]
while cur_l < l:
mo -= a[cur_l]
cur_l += 1
while cur_r > r:
mo -= a[cur_r]
cur_r -= 1
kq[idx] = mo
return kq
for i in mo_s_algorithm(q):
print(i)
```
:::
---
## :bangbang: Chủ đề 2: Bài toán tìm min-max trên đoạn tịnh tiến
:::warning
Cho trước một mảng $A$ có $N$ phần từ, đối với mỗi đoạn con liên tiếp có chiều dài là $K$, ta sẽ phải tìm phần tử min hoặc max trên các đoạn này lần lượt từ trái sang phải (hoặc phải sang trái). Ta có một số nhận xét sau:
- Số lượng truy vấn lớn nhất là $N-K+1$.
- Nếu với mỗi truy vấn, ta lại đi tìm min-max trong đoạn thì độ phức tạp vô cùng lớn và không hiệu quả.
- Giả sử với bài toán tìm max, ta cần một cấu trúc dữ liệu lưu lại được một dãy giảm ngặt với phần tử đứng đầu là max ở truy vấn trước đó, ví dụ với mảng $A=[5,6,2,4,3]$ và $K=3$:
- Mảng con đầu tiên là $A=[5,6,2]$, dãy giảm ngặt là $[6,2]$, và $max=6$
- Mảng con đầu tiên là $A=[6,2,4]$, dãy giảm ngặt là $[6,4]$, và $max=6$
- Mảng con đầu tiên là $A=[2,4,3]$, dãy giảm ngặt là $[4,3]$, và $max=4$
- Ta có thể thấy rằng dãy giảm ngặt ta lưu lại luôn có phần tử ở trái cùng (front) là đáp án, các phần tử ở phía sau lần lượt là phần tử lớn nhất so với phần tử trước nó trong mảng con đang xét.
:100: Nếu yêu cầu bài toán không phải là tìm min-max mà chỉ đơn thuần là đếm hay tính tổng trên các đoạn tịnh tiến thì ta cũng không cần thiết phải sử dụng thuật toán nêu dưới đây.
:::
:::success
:bulb: Để lưu trữ được dãy giảm ngặt đó, ta sẽ cần dùng đến một cấu trúc dữ liệu có tên là **dequeue** (hàng đợi hai đầu) - là một sự kết hợp của ngăn xếp và hàng đợi.
:::
:::success
:::spoiler :key: **Đáp án Sử dụng Dequeue**
```python=
from collections import deque
def tim_max(a, k):
dq = deque()
result = []
for i in range(len(a)):
# Loại bỏ các phần tử có giá trị nhỏ hơn hoặc bằng arr[i]
while dq and a[dq[-1]] <= a[i]:
dq.pop()
# Đẩy phần tử i vào deque
dq.append(i)
# Nếu phần tử đầu tiên trong deque nằm ngoài khoảng tính
# thì ta sẽ loại bỏ ra khỏi deque
if dq and dq[0] + k <= i:
dq.popleft()
# Lấy giá trị lớn nhất trong đoạn đang xét
if i >= k - 1:
result.append(a[dq[0]])
return result
A = [5, 6, 2, 4, 3]
K = 3
print(tim_max(A, K))
```
:::
### :checkered_flag: Bài tập
:::info
Trong một round đấu, rồng thần có thể tấn công tối đa đạt $N$ phát chí mạng vào team địch. Sát thương chí mạng của lần thứ $i$ gây ra là $A_i$. Tuy nhiên rồng thần cần có một khoảng thời gian để hồi lại mana. Vậy nên rồng thần không thể tấn công $K$ lần chí mạng liên tiếp. Bạn hãy điều khiển sức mạnh của rồng thần sao cho tổng sát thương chí mạng gây ra của rồng thần là lớn nhất.
:::
- Input:
- Dòng thứ nhất: chứa hai số nguyên $1 \leq N \leq 10^5$; $2 \leq K \leq 10^5$
- Dòng thứ hai chứa $N$ số nguyên $A_1,...,A_N$ $(1 \leq A_i \leq 10^4)$ là sát thương chí mạng lần tấn công thứ $i$ của rồng thần.
- Output: Tổng sát thương chí mạng lớn nhất mà rồng thần có thể gây ra.
| Input | Output | Giải thích |
| - | - | - |
| 7 3<br />1 4 2 3 6 5 9 | 23 | Rồng thần sẽ tấn công ở những thời điểm 1, 2 rồi 4, 5 sau cùng là 7. Tổng sát thương sẽ là 1+4+3+6+9=23. |
:::success
:::spoiler :key: **Đáp án Sử dụng Quy hoạch động**
:bulb: Đây là gợi ý sử dụng quy hoạch động để giải quyết bài toán này. Tuy nhiên nếu $K$ lớn thì thuật toán sẽ chạy khá chậm. Do đó, bạn có thể kết hợp với kỹ thuật **tìm min trên đoạn tịnh tiến** để tối ưu thêm cho thuật toán.
```python=
def max_damage(N, K, A):
A.append(0)
dp = [float('inf')] * (N + 2)
ans = sum(A)
dp[0] = 0
for i in range(1, N + 2):
for j in range(max(0, i - K), i):
dp[i] = min(dp[i], dp[j] + A[i - 1])
return ans - dp[N + 1]
N, K = 7, 3
A = [1, 4, 2, 3, 6, 5, 9]
print(max_damage(N, K, A))
```
:::
---
## :bangbang: Chủ đề 3: Cây Fenwick (Cây BIT)
:::warning
Việc sử dụng cấu trúc dữ liệu này sẽ giúp ta giải quyết được bài toán:
- Thực hiện $Q$ câu truy vấn tìm tổng các phần tử trong đoạn từ $[L; R]$.
- Có truy vấn dạng ghi dưới dạng cộng/trừ/... một giá trị $u$ vào một phần tử nào đó trên mảng.
:::
### :books: Ý tưởng
Một trong những kỹ thuật đơn giản nhất để xử lý loại bài này là dùng **mảng tổng tiền tố**. Tuy nhiên sẽ sẽ gặp vấn đề ở bước cập nhật, *tất cả những tổng tiền tố nào chứa phần tử được cập nhật sẽ đều phải cập nhật lại*. Sẽ ra sao nếu đề bài luôn cho cập nhật **phần tử đầu tiên**???
:::success
Trong phần này, ta sẽ cố tìm cách tối ưu cách tiếp cận này sao cho việc cập nhật phần tử ít gây ra ảnh hưởng nhất có thể.
:::
Ta có biểu diễn dưới dạng nhị phân của các chỉ số như sau:
Từ ý tưởng này, ta sẽ đi tách blocks để tính toán, để sau cùng, ta được một biểu diễn như sau, tốt hơn nhiều so với biểu diễn của mảng tổng tiền tố.
### :books: Cài đặt
:::warning
Quay lại vấn đề cài đặt, minh hoạ trên đây sử dụng chỉ số mảng bắt đầu từ 1. Tuy nhiên để tiện cho việc đọc hiểu và cài đặt, từ đây tôi sẽ quy ước mảng sẽ có chỉ số bắt đầu từ 0.
:::
:100: Như vậy thấy ta có 2 việc cần thực hiện:
- Xây dựng mảng $bit$ sao cho mỗi giá trị trong mảng này ứng với tổng của một số phần tử trong mảng gốc theo một công thức quy ước.
- Tính toán $sum$ từ mảng $bit$.
:::info
Hãy tưởng tượng mảng $A = \{11,33,22,44,77,55,66,88\}$, mảng $bit$ sẽ xây dựng như sau:
- $bit[0] = 11$ (index = **000**)
- $bit[1] = 11 + 33 = 44$ (index = 000 + **001**)
- $bit[2] = 22$ (index = **010**)
- $bit[3] = 11 + 33 + 22 + 44 = 110$ (index = 000 + 001 + 010 + **011**)
- $bit[4] = 77$ (index = **100**)
- $bit[5] = 77 + 55 = 132$ (index = 100 + **101**)
- $bit[6] = 66$ (index = **110**)
- $bit[7] = 11 + 33 + 22 + 44 + 77 + 55 + 66 + 88 = 396$ (index = 000 + 001 + 010 + 011 + 100 + 101 + 110 + **111**)
:::
:::success
:bulb: Có một điều dễ thấy là index (000) xuất hiện tại $bit[0]$ (000), $bit[1]$ (00**1**), $bit[3]$ (0**11**) và $bit[7]$ (**111**), index (010) xuất hiện tại $bit[2]$ (010), $bit[3]$ (0**11**) và $bit[7]$ (**111**),...
Như vậy, ta nhận xét được rằng nếu ta thay bit 0 trong chỉ số của phần tử thành số 1, ta sẽ được vị trí xuất hiện tiếp theo của phần tử đó trong mảng $bit$
:::
:::success
:::spoiler :key: **Thêm các phần tử vào mảng `bit`**
```python=
n = 8
A = [11, 33, 22, 44, 77, 55, 66, 88]
bit = [0]*n
def add(i, v):
while i < n:
bit[i] += v
i = i | (i+1)
for i, v in enumerate(A):
add(i, v)
print(bit)
```
:::
:::success
:::spoiler :key: **Thêm các phần tử vào mảng `bit` (cải tiến)**
```python=
n = 8
A = [11, 33, 22, 44, 77, 55, 66, 88]
bit = [0]*n
for i, v in enumerate(A):
bit[i] += v
r = i | (i + 1)
if r < n:
bit[r] += bit[i]
print(bit)
```
:::
:::info
Sau khi xây dựng mảng $bit$, ta sẽ sử dụng mảng này để tính toán các giá trị $sum(r)$. Lưu ý: $sum(l, r) = sum(r) - sum(l-1)$ với $l>0$.
:::
:::success
:::spoiler :key: **Tính tổng các phần tử từ mảng `bit`**
```python=
n = 8
A = [11, 33, 22, 44, 77, 55, 66, 88]
bit = [0]*n
for i, v in enumerate(A):
bit[i] += v
r = i | (i + 1)
if r < n:
bit[r] += bit[i]
def sum(r):
kq = 0
while r >= 0:
kq += bit[r]
r = (r & (r + 1)) - 1
return kq
print(bit)
print(sum(2))
```
:::
### :books: Xử lý thao tác cập nhật
:::info
Đối với thao tác **cập nhật 1 phần tử duy nhất** (cập nhật điểm), chỉ có một số đỉnh trên cây BIT thay đổi, do đó, ta có thể xem xét sử dụng lại hàm `add(i, v)` đã cho ở trên.
:::
:::info
Đối với thao tác **cập nhật một số phần tử trên đoạn từ $[a,b]$**, ta cập nhật tại 2 điểm biên như sau:
```python=
add(a, v)
add(b+1, -v)
```
:::
## :bangbang: Chủ đề 4: Cây phân đoạn (Segment tree)
:::warning
Đúng với tên gọi, cây phân đoạn dựa trên ý tưởng **chia để trị**: chia mảng ban đầu thành các đoạn con, tính toán trên các đoạn này và cuối cùng là "hợp nhất" các kết quả tính toán trên các đoạn nhỏ đó để trả lời một truy vấn $Q$ trên đoạn $[L; R]$ cho trước.
Tương tự như cây BIT, cây phân đoạn xử lý tốt các truy vấn ở dạng đọc và ghi trên mảng. Nhưng với một ý tưởng đơn giản và dễ hiểu hơn... song, việc cài đặt cây phân đoạn sẽ hơi dài dòng hơn một chút.
:::
:::info
Xét mảng $a = [1, 3, -2, 8, -7]$ với $N=5$, ta sẽ xây dựng cây phân đoạn để xử lý truy vấn tính tổng như sau:
Dễ thấy, cây phân đoạn là một cây nhị phân đầy đủ (full binary tree) vì mỗi nút luôn có 0 hoặc 2 nút con.
- Mức thứ 1 có 1 nút.
- Mức thứ 2 có 2 nút.
- Mức thứ 3 có 4 nút.
- ...
- Mức thứ $\lceil log_2(N) \rceil +1$ có nhiều nhất $2^{\lceil log_2(N) \rceil}$ nút
Như vậy tổng số nút sẽ không vượt quá $2^{\lceil log_2(N) \rceil + 1}$ nút. Hay để cho đơn giản, ta sẽ nói tổng số nút không vượt quá $4*n$ nút.
:::
### :books: Cài đặt
:::warning
Quay lại vấn đề cài đặt, trực quan của cấu trúc dữ liệu này khá đơn giản và dễ nhìn. Để cho đơn giản, ta sẽ dùng một mảng có độ dài tối đa là $4n$ để lưu trữ tất cả các nút của cây.
Nếu ta gọi $i$ là nút cha thì 2 nút con sẽ có vị trí trong mảng là:
- Nút con bên trái: $2*n + 1$
- Nút con bên phải: $2*n + 2$
:::
:::info
Việc tính toán ra các giá trị $sum$ để xây dựng cây phân đoạn cũng sẽ khá đơn giản (sử dụng đệ quy hoặc vòng lặp đều được). Việc tính toán sẽ bắt đầu từ nút gốc (chỉ số mảng là 0) và lan dần đến các cây con và quay lại cập nhật giá trị cho gốc...
:::
:::success
:::spoiler :key: **Xây dựng cây phân đoạn**
```python=
N = 5
a = [1, 3, -2, 8, -7]
# Mảng chứa cây phân đoạn
seg = [0] * (4 * N)
# Mặc định build từ nút gốc (idx=0)
def build(idx=0, l=0, r=N-1):
if l == r:
# idx là nút lá
seg[idx] = a[l]
else:
# idx có 2 con
m = (l + r) // 2
# đệ quy cây con trái
build(idx*2+1, l, m)
# đệ quy cây con phải
build(idx*2+2, m+1, r)
# cập nhật lại giá trị của idx
seg[idx] = seg[idx*2+1] + seg[idx*2+2]
build()
print(seg)
# [3, 2, 1, 4, -2, 8, -7, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```
:::
:::info
Việc tính tổng các phần tử cũng không quá phức tạp: ta cũng bắt đầu duyệt từ nút gốc, lần lượt tìm ra các cây mà đoạn $[L; R]$ bao phủ.
:::
:::success
:::spoiler :key: **Tính tổng các phần tử từ cây phân đoạn**
```python=
def sum(L, R, idx=0, l=0, r=N-1):
if L > R:
return 0
if L == l and R == r:
return seg[idx]
m = (l + r) // 2
return (sum(L, min(R, m), idx*2+1, l, m) +
sum(max(L, m+1), R, idx*2+2, m+1, r))
print(sum(2, 4)) # -1
```
:::
### :books: Xử lý thao tác cập nhật điểm
:::info
Đối với thao tác **cập nhật 1 phần tử duy nhất** (cập nhật điểm), sẽ có một số nút trên cây thay đổi, do đó, ta có thể xem xét sử dụng lại ý tưởng như hàm `build()` kết hợp thêm thao tác kiểm tra phần cây bên nào bị ảnh hưởng; đương nhiên, ta không quên cập nhật lại giá trị cho nút cha.
:::
:::success
:::spoiler :key: **Cập nhật điểm trên cây phân đoạn**
```python=
def update(i, v, idx=0, l=0, r=N-1):
if l == r:
seg[idx] = v
else:
m = (l + r) // 2
# Tìm ra cây bị ảnh hưởng
if i <= m:
update(i, v, idx*2+1, l, m)
else:
update(i, v, idx*2+2, m+1, r)
# Cập nhật lại giá trị cho nút cha
seg[idx] = seg[idx*2+1] + seg[idx*2+2]
update(2, 3)
print(seg)
# [8, 7, 1, 4, 3, 8, -7, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```
:::
https://oj.vnoi.info/problem/segtree_itez2
### :books: Mở rộng
:::info
Ngoài việc tính tổng trên đoạn, nhờ vào tính linh hoạt, cây phân đoạn còn có thể dùng cho bài toán đếm, tìm min-max,... thậm chí là một số bài toán như:
- Tính toán UCLN/BCNN cho một mảng số (gộp nút bằng hàm `gcd(a, b)` hoặc `lcm(a, b)`
- Đếm số lượng số 0, tìm số 0 thứ $k$ trong mảng
- Tìm phần tử đầu tiên trong đoạn $[L; R]$ có giá trị lớn hơn $x$
- ...
Nói chung, tuỳ vào yêu cầu bài toán mà ta chọn dữ liệu lưu trữ trên nút và cách gộp nút sao cho phù hợp.
:::
### :books: Xử lý thao tác cập nhật đoạn
:::info
Đối với thao tác **cập nhật các phần tử trên đoạn $[a,b]$**, ta sẽ sử dụng chiến lược Lazy Propagation.
:::
:::success
:::spoiler :key: **Cập nhật đoạn trên cây phân đoạn**
```python=
```
:::
https://oj.vnoi.info/problem/qmax2
## :bangbang: Chủ đề 5: Bảng thưa (Sparse Table)
:::warning
Đây là một cấu trúc dữ liệu đơn giản cho phép thực hiện các truy vấn dạng đọc ở trên đoạn khá hiệu quả. Tuy nhiên, nhược điểm của cấu trúc này là không thực hiện được các truy vấn dạng ghi; tức là, mảng không được phép thay đổi.
:::
Sign in with Wallet
Connect another wallet