Cấu trúc bảng thưa thớt (Sparse Table)

Please support me and buy me a coffee, much thanks!

Tưởng tượng như ta phải xử lý một vấn đề sau:

Cho một mảng A. Thực hiện một số lượng truy vấn như sau:

Mỗi truy vấn gồm 2 số (l, r) (1 <= l, r <= A.length). Hãy tìm:

• Giá trị (hoặc chỉ số) của phần tử nhỏ nhất trong đoạn [l, r]
• Giá trị (hoặc chỉ số) của phần tử lớn nhất trong đoạn [l, r]

Như ta đã biết, vấn đề này hoàn toàn có thể xử lý với segment tree, với độ phức tạp thời gian O(N*log(N)) để khởi tạo, O(log(N)) để trả lời truy vấn, và độ phức tạp không gian là O(4*N).

Bài viết này sẽ cung cấp một phương pháp giải khác – sử dụng cấu trúc Sparse Table (bảng thưa thớt – ở đây viết tắt là SpT nhằm phân biệt với ST của segment tree): với độ phức tạp thời gian O(N*log(N)) để khởi tạo, O(1) để trả lời truy vấn, và độ phức tạp không gian là O(N*log(N)).

Khi nào dùng segment tree và khi nào dùng sparse table?

Ta sẽ cân nhắc dựa vào bản chất, yêu cầu bài toán. Thông thường, thao tác cập nhật của segment tree có độ phức tạp O(log(N)) (với 1 phần tử, với một mảng lớn thì thao tác sẽ là O(log(N)) nếu có cài đặt lan truyền lười nhác), còn với sparse table thì độ phức tạp là O(N*log(N)) (cập nhật toàn bộ).

Do đó, sparse table phù hợp với việc biểu diễn dữ liệu “tĩnh” hơn.

Xây dựng SpT từ array

SpT của chúng ta sẽ là một mảng chứa các mảng (không phải mảng 2 chiều, vì kích thước các mảng con không đồng nhất mà sẽ adaptive theo độ dài – trong C++ ta có thể biểu diễn bằng std::vector lồng vào nhau, hoặc để đơn giản cũng có thể sử dụng mảng 2 chiều, chấp nhận chứa các phần tử dư).

Nguyên tắc thực hiện sẽ là: với array A[] ban đầu có kích thước N, mỗi phần tử SpT[i][j] (chỉ số đánh số từ 0) sẽ là giá trị cần thu được trên khoảng [i, i+2^j-1] của A[] (i+2^j-1 < N).

Xét trường hợp đề bài yêu cầu tìm minimum trên khoảng, lúc này ta sẽ có hệ thức:

• SpT[i][0] = A[i].
• SpT[i][k] = min(SpT[i][k-1], SpT[i+2^(k-1)][k-1]) (với k > 0).

Các trường hợp khác (sum, max, GCD, etc.) thực hiện tương tự.

Trả lời truy vấn

Tiếp tục xét yêu cầu trả về min.

Ta nhận thấy, với sparse table, giờ đây thay vì so sánh từng phần tử trong vùng cần xét như phương pháp khờ khạo, ta chỉ cần tìm ra 2 giá trị trên sparse table, sao cho hợp vùng biểu diễn của 2 giá trị này đúng bằng vùng biểu diễn của toàn truy vấn (chúng ta sẽ không quan tâm tới giao trong trường hợp min/max/GCD).

Tổng quát hơn, kết quả truy vấn sẽ là giá trị min của SpT[l][j] và SpT[r+1-2^j][j], với j là số tự nhiên lớn nhất thỏa mãn 2^j <= r-l+1. Tức là, ta sẽ so sánh khoảng tiền tố có độ dài 2^j và khoảng hậu tố có độ dài 2^j; và với việc j lớn nhất có thể mà không vượt ra khỏi vùng truy vấn, ta dễ dàng chứng minh được hợp của 2 vùng được xét đúng bằng vùng truy vấn ta cần. Độ phức tạp cho phép so sánh là O(1).

Tuy nhiên, j sẽ được xác định như thế nào?

Nếu phải thử từng giá trị của j, thì sparse table trở nên vô dụng, vì quá trình này đẩy độ phức tạp từ O(1) trở về O(log(N)) như segment tree.

Tuy nhiên, ta có thể giải quyết quá trình này thông qua một bước tiền xử lý nữa.

Gọi Log2[] là array lưu phần nguyên của các giá trị Log2 từ 1 tới N (hiển nhiên, với định nghĩa ở trên, floor(log2(r-l+1)) = Log2[r-l+1] = j. Ta có thể tính toán toàn bộ các giá trị này theo xử lý khờ khạo như trên với độ phức tạp O(N*log(N)) – tức là cũng tương đồng với quá trình khởi tạo sẵn SpT ở trên. Ưu điểm ở đây là, ta sẽ không phải tính lại giá trị này khi xử lý truy vấn.

Mở rộng: Nếu yêu cầu của truy vấn là tìm tổng phần tử trên đoạn?

Lúc này, thay vì so sánh 2 khoảng như ở trên, ta sẽ thực hiện cộng dần từ đầu tới cuối với độ phức tạp O(log(N)): chừng nào l <= r thì cộng thêm vào kết quả một giá trị bằng SpT[l][j], rồi gán lại l := l + 2^j.

Thực ra, với một mảng tĩnh, việc tìm truy vấn tổng sẽ đơn giản hơn nếu ta sử dụng prefix sum, tuy nhiên đây cũng là một phương pháp có thể tham khảo.

Bài toán tham khảo 1: SPOJ-RMQSQ

Lời giải: Ideone.com

Bài toán tham khảo 2: VNSPOJ-QMAX

Lời giải: Ideone.com

Bài toán tham khảo 3: VNSPOJ-NKLINEUP

Lời giải: Ideone.com

#Akikaze

Featuring #ThuyTrang_12A2

Thư viện code

Code tổng hợp từ các bài viết trên thuytrangcoding, đồng thời với những code do #Team4T viết nhưng chưa đăng trên bài viết nào (do chưa thể viết được chủ đề).

Bài viết có mục đích tổng hợp và tham khảo.

I. Tham lam

1. Bài toán lịch họp (scheduling)

Link bài: PTIT127C – Bố trí phòng họp

Source code: Ideone.com

2. Bài toán tổng chênh lệch tối thiểu (hàm tuyến tính)

Link bài: P187PROI – ROUND 7I – MÁI NHÀ

Source code: Ideone.com

II. Đồ thị

1. Đường đi ngắn nhất

a. Dijkstra

Link bài: Codeforces 20C – Dijkstra?

Source code: Submission 33253245

b. Floyd:

Link bài: CS Academy – Round 70 – Min Distances

Source code: CS Academy – Submission 1370237

2. Cây khung nhỏ nhất

Link bài: VNSPOJ-QBMST

a. Prim: Ideone.com

b. Kruskal: Ideone.com

3. Topological sorting

Link bài: Codeforces 919D – Substring

Source code: Submission 34788171

4. Thành phần liên thông mạnh (SCC)

Link bài: VNSPOJ-TJALG

a. Kosaraju: Ideone.com

b. Tarjan: Ideone.com

III. Cấu trúc dữ liệu

1. Cây tiền tố (Prefix Tree / Trie)

Link bài: P176PROC – ROUND 6C – GOOD OR BAD? (SPOJ – PTIT)

Source code: Ideone.com

2. Cây phân đoạn (Segment Tree)

a. Cơ bản:

Link bài 1: VNSPOJ-QMAX

Source code: Ideone.com

Link bài 2: Codeforces 920F – SUM and REPLACE

Source code: Submission 35221937

b. Lazy Propagation:

Link bài: VNSPOJ-QMAX2

Source code: Ideone.com

IV. Xử lý xâu

1. So khớp chuỗi

Link bài: VNSPOJ-SUBSTR

a. KMP: Ideone.com

b. Z: Ideone.com

c1. Hashing (đơn module): Ideone.com

c2. Hashing (đa module): Ideone.com

2. Hashing

a. Longest Palindromic Substring:

Link bài: VNSPOJ-PALINY

Source code (đơn module): Ideone.com

Source code (đa module): Ideone.com

V. Hình học

1. Bao lồi

Link bài: Kattis Problem – Convex Hull

Source code: Ideone.com

Giải bài toán đường đi ngắn nhất bằng thuật toán Bellman-Ford

Đây là hướng dẫn sử dụng thuật toán Bellman-Ford. Xem thêm:

• Sơ lược về bài toán đường đi ngắn nhất.
• Thuật toán Floyd-Warshall
• Thuật toán Dijkstra

Thuật toán Bellman-Ford là một trong những thuật toán dùng để tìm đường đi ngắn nhất (chỉ áp dụng cho đồ thị có hướng) từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện đồ thị không được phép có chu trình âm.

Trước hết, về khâu tổ chức dữ liệu: ta xây dựng một mảng 1D chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF.

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V).

Ý tưởng thuật toán Bellman-Ford có tính tham lam:

• Ta thực hiện duyệt V lần, với V là số đỉnh của đồ thị.
• Với mỗi lần duyệt, ta tìm tất cả các cạnh mà đường đi qua cạnh đó sẽ rút ngắn đường đi ngắn nhất từ đỉnh gốc tới một đỉnh khác.
• Ở lần duyệt thứ V, nếu còn bất kỳ cạnh nào có thể rút ngắn đường đi, điều đó chứng tỏ đồ thị có chu trình âm, và ta kết thúc thuật toán.

Tính đúng đắn của ý tưởng này được chứng minh quy nạp.

Ta có khẳng định sau: Ở thời điểm mà ta đã đi qua i lần duyệt thì những mệnh đề sau được coi là đúng:

• Nếu khoảng cách từ điểm gốc tới 1 điểm u không phải là +INF, thì khoảng cách đó đúng bằng độ dài 1 đường đi nào đó từ gốc tới u.
• Với đỉnh u đó, nếu tồn tại đường đi từ gốc tới u mà đi qua tối đa i cạnh, thì độ dài đường đi ngắn nhất sẽ không vượt quá độ dài đường đi kể trên.

Quá trình chứng minh quy nạp:

• Trường hợp cơ bản: i = 0. Ta chưa duyệt qua lần nào, nên cả 2 điều đều hiển nhiên đúng (Đường đi ngắn nhất tới đỉnh gốc bằng 0, hiển nhiên vì điểm xuất phát và đích trùng nhau, còn đường đi ngắn nhất tới các đỉnh khác bằng +INF vì ta không có bất kỳ đường đi nào được tìm thấy để tới chúng).
• Trường hợp quy nạp:
  • Mệnh đề 1 rõ ràng đúng. Ta tưởng tượng, nếu trong quá trình duyệt cạnh, xuất hiện cạnh (u, v) với trọng số w có thể tối ưu hóa đường đi ngắn nhất của v được, thì đương nhiên ta cập nhật độ dài đó: dist[v] = dist[u] + w. Rõ ràng dist[v] là độ dài một đường đi từ gốc tới v, hay chính xác hơn là đường đi từ gốc tới u, rồi đi qua cạnh (u, v) tới v.
  • Với mệnh đề 2, ta tiếp tục sử dụng giả sử về cạnh (u, v) trọng số w như ở trên. Với giả thuyết quy nạp, dist[u] sẽ không vượt quá độ dài bất kỳ đường đi từ gốc tới u mà đi qua tối đa (i-1) cạnh. Do đó, cộng đồng thời 2 vế, ta sẽ có (dist[u] + w_min) không vượt quá độ dài bất kỳ đường đi nào từ gốc tới u với lượng cạnh không quá (i-1), rồi đi qua cạnh (u, v). Hay nói cách khác, không có đường đi nào từ gốc tới v với lượng cạnh không quá i (khớp với giả thuyết quy nạp).

Ta lại nhận thấy, đường đi ngắn nhất hiển nhiên không có chu trình (nên nhớ rằng ta không xét chu trình âm, vì nó sẽ khiến đường đi kéo dài vô tận và độ dài tiến tới -INF, còn nếu chu trình không âm thì việc đi lặp lại chu trình vô nghĩa), vậy nên một đường đi giữa 2 đỉnh sẽ chỉ có tối đa V-1 cạnh.

Vậy nên, thuật toán Bellman-Ford sẽ chỉ cần V lần duyệt cạnh – lần duyệt thứ V sẽ là lần duyệt để kiểm tra chu trình âm: Nếu có đường đi được cập nhật mới ở lần duyệt này, hẳn là đã có 1 đường đi tối ưu nào đó có V cạnh – điều này là vô lý với đồ thị không có chu trình âm.

Độ phức tạp của thuật toán sẽ là O(VE) – khá lớn, nên nếu đồ thị không có cạnh có trọng số âm, thuật toán Dijkstra sẽ là một hướng tiếp cận hữu dụng hơn.

 

Ta xét ví dụ với đồ thị có hướng sau (giả định các đường đi là một chiều, chỉ đi từ đỉnh có số thứ tự thấp hơn tới đỉnh có số thứ tự cao hơn, số có màu đỏ cạnh mỗi đỉnh là độ dài đường đi ngắn nhất từ gốc tới đỉnh đó, và đỉnh gốc là đỉnh 1):

Thực hiện lần duyệt đầu tiên, ta cập nhật được đường đi ngắn nhất thông qua các cạnh (1, 2); (1, 3); (1, 4):

Tương tự với lần duyệt thứ 2, cạnh (2, 5) và (3, 4) là các cạnh tối ưu:

Với lần duyệt thứ 3, chỉ có cạnh (4, 5) cải tiến đường đi tối ưu:

Tới lần duyệt thứ 4, ta thấy không còn cạnh nào có thể tối ưu hóa bất kỳ đường đi ngắn nhất nào nữa. Tới đây, ta hoàn toàn có thể dừng duyệt (vì chắc chắn việc không còn cạnh có thể tối ưu cũng đồng nghĩa với việc không có chu trình âm trong đồ thị).

 

Ta có thể cài đặt thuật toán như sau:

Hoặc bạn có thể tham khảo source code của anh Nguyễn Tiến Trung Kiên (kc97ble).

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Giải bài toán đường đi ngắn nhất bằng thuật toán Dijkstra

Đây là hướng dẫn sử dụng thuật toán Dijkstra. Xem thêm:

• Sơ lược về bài toán đường đi ngắn nhất.
• Thuật toán Floyd-Warshall
• Thuật toán Bellman-Ford

Thuật toán Dijkstra là một trong những thuật toán cơ bản dùng để tìm đường đi ngắn nhất từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện các trọng số của đồ thị đó không âm.

Trước hết, về khâu tổ chức dữ liệu: ta xây dựng một mảng 1D chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF.

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V).

Ta xét đồ thị vô hướng sau (số màu đỏ là đường đi ngắn nhất xuất phát từ đỉnh 1 tới đỉnh được xét):

Quá trình thực hiện thuật toán Dijkstra sẽ diễn ra như sau:

• Chọn một điểm bất kỳ chưa được duyệt và có đường đi ngắn nhất từ điểm gốc tới nó là nhỏ nhất.
• Từ điểm đó, loang đường đi ra tất cả các đỉnh kề cận, và cập nhật lại đường đi ngắn nhất tới các đỉnh đó nếu đường đi mới tối ưu hơn.
• Nếu còn điểm chưa được duyệt (hoặc chưa tìm được điểm đích, tùy yêu cầu đề bài), ta trở lại bước 1.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, ta xét đỉnh 1 (vì đường đi ngắn nhất từ 1 tới 1 hiển nhiên có độ dài 0).

Sau quá trình cập nhật, ta có các giá trị đường đi ngắn nhất mới: 

Tiếp theo, ta duyệt đỉnh 5 (đường đi ngắn nhất từ 1 tới 5 có độ dài 1).

Sau cập nhật, ta thu được các giá trị mới:

Tiếp theo, ta duyệt đỉnh 4 (đường đi ngắn nhất từ 1 tới 4 có độ dài 3).

Sau cập nhật, ta thu được các giá trị mới:

Cứ tiếp tục như vậy cho tới khi duyệt hết đỉnh, ta sẽ thu được các giá trị hoàn chỉnh:

Sở dĩ phương pháp tham lam này đúng bởi, ta đã ngầm định đặt ra điều kiện trước: các trọng số của các cạnh phải là các số không âm. Do đó, việc duyệt liên tục từ các đỉnh có độ dài đường đi ngắn nhất là cực tiểu sẽ luôn được đảm bảo tính chính xác: ta không thể xuất phát từ bất kỳ đỉnh nào khác qua một giá trị trung gian mà thu được đường đi nhỏ nhất từ đỉnh gốc tới đỉnh cực tiểu ta đang xét thậm chí còn nhỏ hơn nữa được.

Tuy nhiên, với trường hợp trọng số âm, lập luận này bị bác bỏ. Xét đồ thị sau:

Bằng mắt thường, ta có thể thấy rằng: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 4 sẽ là đoạn đường 1->3->4.

Tuy nhiên, áp dụng tư duy thuật toán Dijkstra, ta có:

• Khởi tạo: s_path[1] = 0, s_path[2] = INF, s_path[3] = INF, s_path[4] = INF.
• Xuất phát từ đỉnh 1. Cập nhật: s_path[2] = 2, s_path[3] = 6.
• Xuất phát từ đỉnh 2. Cập nhật: s_path[4] = 5.
• Xuất phát từ đỉnh 4. Do đây là đỉnh đích nên ngừng thuật toán, kết luận ans = 5.

Rõ ràng, do phương pháp tham lam không tính đến trường hợp độ dài đường đi nhỏ nhất có thể giảm, nên nhánh xuất phát từ đỉnh 3 bị loại bỏ, dẫn đến kết quả sai.

 

Một phép cài đặt thuật toán Dijkstra thành công được quyết định chủ yếu bởi độ phức tạp của quá trình tìm đỉnh tiếp theo được duyệt.

Với phương pháp khờ khạo, độ phức tạp của quá trình này sẽ là O(V), do đó độ phức tạp của thuật toán trở thành O(V^2).

Ta có thể cải tiến quá trình này thông qua hàng đợi ưu tiên – giúp độ phức tạp của quá trình tìm kiếm đỉnh chỉ biến thiên theo hàm logarithm.

Một ví dụ về việc cài đặt như sau:

Ta nhận thấy, trong cách cài đặt này, trong hàng đợi sẽ chứa độ dài cạnh với giá trị âm. Sở dĩ vậy là bởi, priority_queue của C++ sẽ ngầm định trả về giá trị lớn nhất ở đầu hàng đợi, mà ta lại cần giá trị nhỏ nhất. Tất nhiên, ta có nhiều cách khác để xử lý, như thay đổi toán tử so sánh cho priority_queue, sử dụng STL set/multiset, v.v. …

Độ phức tạp cho cách cài đặt trên là O(E+V*log V).

 

Bài toán tham khảo: Codeforces 20C – Dijkstra?

Tóm tắt đề bài:

Cho 1 đồ thị vô hướng có trọng số gồm N đỉnh và M cạnh. Hãy tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh N.

Nếu không có đường đi, in ra -1.

Nếu có nhiều đường đi cùng trả về 1 giá trị tối ưu, có thể tùy chọn đường đi.

Phương pháp:

Đây là một bài tập căn bản cho thuật toán Dijkstra. Có một số điểm cần lưu ý:

• Output sẽ trả về -1 nếu sau khi kết thúc duyệt, đường đi ngắn nhất từ 1 tới N là +INF (nhớ rằng đề bài không đảm bảo đồ thị là liên thông).
• Vì ta phải in ra đường đi nên ngoài việc xác định giá trị đường đi nhỏ nhất, ta còn phải thực hiện truy vết. Phương pháp truy vết thì vẫn tương tự như khi duyệt DFS/BFS thông thường.

Lời giải (của D.Bách): Submission 33253245

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Giải bài toán đường đi ngắn nhất bằng thuật toán Floyd-Warshall

Đây là hướng dẫn sử dụng thuật toán Floyd-Warshall. Xem thêm:

• Sơ lược về bài toán đường đi ngắn nhất.
• Thuật toán Dijkstra
• Thuật toán Bellman-Ford

Trong những bài toán đường đi ngắn nhất mà chúng ta cần thông tin về đường đi giữa nhiều cặp đỉnh, ta có xu hướng là sẽ tính toán đường đi ngắn nhất giữa mọi cặp đỉnh.

Thuật toán Floyd-Warshall là một thuật toán phù hợp để thực hiện tác vụ này.

Trước hết, ta cần phải nắm về khâu tổ chức dữ liệu: đường đi ngắn nhất giữa 2 đỉnh bất kỳ sẽ được lưu trong một mảng 2 chiều, ngầm định sẽ có giá trị là +INF nếu không có đường nối trực tiếp giữa chúng, hoặc nếu có đường nối thì giá trị ban đầu sẽ là trọng số của đường nối đó. Các tính toán sau này sẽ là so sánh giữa đường đi ngắn nhất hiện tại với một đường đi trung gian (giả sử, với 2 đỉnh A và B, ta so sánh đường đi ngắn nhất hiện thời giữa 2 đỉnh này với tổng độ dài đường đi ngắn nhất từ A và từ B tới 1 đỉnh C trung gian nào đó).

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V^2).

Ta xét đồ thị vô hướng sau: 

Từ quy tắc trên, mảng 2D chứa đường đi ngắn nhất ban đầu sẽ được khởi tạo như sau:

Từ đây, quá trình thực hiện thuật toán Floyd-Warshall sẽ diễn ra như sau:

• Chọn lần lượt từng đỉnh của đồ thị làm đỉnh trung gian (ta quy ước là C).
  • Chọn một cặp 2 đỉnh phân biệt và không trùng với đỉnh trung gian (ta quy ước lần lượt là A và B).
    • Thực hiện so sánh như ở trên: đường đi ngắn nhất giữa A và B sẽ bằng giá trị nhỏ nhất của:
      • Giá trị đường đi ngắn nhất hiện thời giữa A và B.
      • Tổng của giá trị đường đi ngắn nhất hiện thời giữa A và C, và đường đi ngắn nhất hiện thời giữa B và C.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, C = 1. Nhờ đỉnh 1 làm trung gian, ta thấy xuất hiện đường đi từ đỉnh 2 tới đỉnh 4 (độ dài 14), và từ đỉnh 2 tới đỉnh 5 (độ dài 6).

Đường đi trung gian qua đỉnh 1 để đi từ đỉnh 4 tới đỉnh 5 không tối ưu về chiều dài (9 + 1 > 2) nên ta không cập nhật lại đường đi ngắn nhất giữa 2 đỉnh 4 và 5.

Mảng 2D lúc này trở thành: 

Tiếp theo, ta duyệt tới C = 2.

Đường đi từ 3 tới 1 (độ dài 7), từ 3 tới 5 (độ dài 8) được hình thành.

Đường đi từ 3 tới 4 không cập nhật độ dài (7 < 2 + 5 + 9).

Mảng 2D lúc này là: 

Cứ tiếp tục lựa chọn C như vậy cho tới hết, ta sẽ thu được mảng 2D hoàn chỉnh:

Giả sử, qua mảng này, ta thấy đường đi ngắn nhất từ đỉnh 2 tới đỉnh 4 có độ dài 8. Dựa theo đồ thị thì nó là đoạn đường sau: 

 

Quá trình cài đặt thuật toán Floyd-Warshall khá đơn giản, có thể chia làm 2 công đoạn:

1. Khởi tạo mảng 2D chứa đường đi ngắn nhất (ở code này thì đồ thị được biểu diễn ở dạng ma trận kề, và distance là tên mảng): 
2. Tính toán giá trị đường đi ngắn nhất: 

Hoàn toàn dễ dàng nhận ra, thuật toán có độ phức tạp O(V^3). Do đó, thuật toán chỉ nên áp dụng với những đồ thị có số đỉnh nhỏ (thường chỉ tới 100-200 đỉnh).

 

Bài toán tham khảo: CS Academy – Round 70 – Min Distances

Tóm tắt đề bài:

Cho 2 số N và M, và M bộ 3 số (a, b, c).

Hãy tạo ra một đồ thị đơn vô hướng, liên thông, có trọng số với N đỉnh, sao cho với mỗi bộ số (a, b, c) đề cập ở trên, đường đi ngắn nhất giữa đỉnh a và đỉnh b phải bằng c.

Mọi cạnh trên đồ thị được in ra có trọng số không quá 10^7.

Nếu không có đồ thị thỏa mãn, in ra -1.

Phương pháp:

Trường hợp duy nhất để không tìm thấy đồ thị thỏa mãn là các cạnh bị ràng buộc chồng chéo lên nhau – theo cách mà 2 cạnh ràng buộc trung gian có độ dài ngắn hơn một cạnh ràng buộc khác.

Ta nhận thấy, ta hoàn toàn có thể lập một đồ thị đầy đủ, với trọng số tất cả các cạnh bằng 10^7. Với mỗi bộ số (a, b, c), ta gán lại trọng số của cạnh (a, b) bằng c.

Như vậy, ít nhất nếu không tính các đường đi gián tiếp, đồ thị ta lập ra vẫn thỏa mãn ràng buộc của đề bài.

Tới đây, ta có thể sử dụng thuật toán Floyd để tìm đường đi ngắn nhất của tất cả các cặp đỉnh trên đồ thị.

Nếu không có bộ số (a, b, c) nào mà đường đi ngắn nhất từ a tới b khác c, thì đồ thị đó là thỏa mãn, và có thể in ra.

Ngược lại, in ra -1.

Lời giải (của neko_nyaa): CS Academy – Submission 1372996

Lời giải (của D.Bách): CS Academy – Submission 1370237

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Bài toán đường đi ngắn nhất

Khái niệm căn bản nhất về loại bài toán này là: với một đồ thị đã cho, ta cần tìm một đường đi giữa 2 đỉnh sao cho độ dài đường đi (tức là tổng trọng số các cạnh trên đường đi đó) là nhỏ nhất có thể.

Có 2 biến thể phổ biến nhất cho dạng bài toán này, đó là:

1. Cố định trước 1 đỉnh, tìm đường đi ngắn nhất từ đỉnh đó tới 1 đỉnh khác bất kỳ.
2. Cho trước đồ thị, yêu cầu tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trên đồ thị đó.

Trong thực tế, có rất nhiều thuật toán được ứng dụng cho loại bài toán này:

1. Tìm đường đi ngắn nhất từ 1 đỉnh cố định:
   • Đối với đồ thị vô hướng:
     • Nếu không có trọng số, hiển nhiên ta sẽ dùng phương pháp duyệt BFS.
     • Nếu có trọng số, ta có thể dùng thuật toán Dijkstra.
       • Độ phức tạp: tùy theo phương thức lưu trữ, thường thấy là O(V^2), O((E + V) log V), O(E + V log V).
   • Với đồ thị có hướng không chu trình (DAG), việc tìm kiếm có thể dễ dàng thực hiện thông qua sắp xếp tô-pô (topological sorting).
     • Độ phức tạp: O(V + E).
   • Với đồ thị có hướng thông thường, trọng số không âm, ngoài việc áp dụng Dijkstra, ta còn có thể dùng thuật toán Bellman-Ford.
     • Độ phức tạp: O(VE)
     • Trong trường hợp một số cạnh có trọng số âm nhưng không có chu trình âm thì ta cũng có thể sử dụng Bellman-Ford.
2. Tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ: Ta sử dụng thuật toán Floyd-Warshall.
   • Độ phức tạp: O(V*f(V,E)), với f(V,E) là độ phức tạp của thuật toán ở mục 1.
   • Nếu sử dụng đúng phương pháp của Floyd-Warshall (không kết hợp các phương pháp ở mục 1 với việc chọn 1 đỉnh làm đỉnh cố định) thì độ phức tạp là O(V^3).

 

#ThuyTrang_12A2

Tìm thành phần liên thông mạnh của đồ thị có hướng bằng thuật toán Tarjan

Đây là hướng dẫn sử dụng thuật toán Tarjan. Đối với phương pháp giải sử dụng thuật toán Kosaraju, xem tại đây.

Trước hết, khái niệm “thành phần liên thông mạnh” (Strongly Connected Components – SCC) được định nghĩa là một tập hợp các đỉnh trên đồ thị có hướng mà từ 1 đỉnh, ta có thể đi đến tất cả các đỉnh còn lại trong tập hợp đó. Ngoài ra, mỗi TPLTM phải là cực đại, nghĩa là không thể thêm bất cứ đỉnh nào vào một TPLTM mà vẫn tạo thành TPLTM.

 

Dĩ nhiên, việc tìm TPLTM của đồ thị có hướng không dễ dàng như tìm TPLT của đồ thị vô hướng. Ví dụ với đồ thị có dạng giản lược sau: (0) -> (1) -> (2) -> (3) – nếu ta tìm TPLTM theo cách của đồ thị vô hướng, thì nếu giả định ta xuất phát từ bất kỳ đỉnh nào không phải (0), thì ta không thể đi tới đỉnh (0) được – tức là kết quả TPLTM tìm được thay đổi theo đỉnh (và thậm chí cũng không chính xác).

 

Chúng ta sẽ tiến tới một cách tiếp cận khác cho bài toán TPLTM – thuật toán Tarjan.

Ý tưởng của thuật toán này dựa trên phương pháp duyệt theo chiều sâu (depth-first search | DFS).

Đầu tiên, ta tạo sẵn một ngăn xếp (stack) – nó có nhiệm vụ lưu trữ các phần tử đang nằm cùng một thành phần liên thông mạnh chưa hoàn chỉnh (tức là vẫn còn có thể có những phần tử khác thuộc chung TPLTM).

Với mỗi đỉnh trên đồ thị, ta lưu 2 thuộc tính: “Enum” dùng để xác định thứ tự được duyệt của đỉnh đó (dựa theo DFS) và “Lowest” dùng để xác định thứ tự nhỏ nhất có thể của đỉnh có thể được đi tới từ đỉnh đó.

Việc xử lý các thuộc tính này trong quá trình DFS diễn ra như sau:

• Trước hết, mỗi khi bắt đầu duyệt một đỉnh, giá trị Enum được gán cố định cho đỉnh đó, và sẽ không đổi trong suốt quá trình. Quy tắc của chúng ta vẫn sẽ là, đỉnh được duyệt trước sẽ có giá trị Enum nhỏ hơn.
• Hiển nhiên, cho tới lúc này Lowest đúng bằng Enum.
• Đặt chỉ số của đỉnh đang xét lên đầu stack.
• Xem xét các đỉnh có thể được đi tới từ đỉnh đang xét:
  • Nếu đỉnh đó đã được duyệt qua (Enum khác giá trị đặt ngầm định) thì hiệu chỉnh giá trị Lowest theo giá trị Lowest của đỉnh đó (chỉ thực hiện khi giá trị đó nhỏ hơn giá trị hiện tại).
  • Nếu chưa được duyệt thì ta thực hiện duyệt đỉnh đó (như bất kỳ một hàm DFS đệ quy thông thường nào), rồi sau đó hiệu chỉnh giá trị Lowest theo quy tắc tương tự ở trên.
• Sau khi kết thúc duyệt một đỉnh, ta kiểm tra Lowest và Enum:
  • Nếu 2 giá trị khác nhau, tức đây không phải đỉnh “gốc” của một TPLTM nào, ta bỏ qua và kết thúc hàm tại đỉnh đó.
  • Ngược lại, tức là ta đã trở về gốc của TPLTM, hay nói cách khác toàn bộ các khả năng duyệt đã được kiểm tra. Tới đây, ta có thể xóa tất cả các đỉnh khỏi stack và đồng thời loại bỏ khỏi việc bị duyệt lại (cách đơn giản nhất là đặt Enum và Lowest tới giá trị dương vô cùng).

Độ phức tạp của thuật toán là O(V+E) (chỉ cần 1 lần DFS trên toàn bộ đồ thị).

 

Bài toán 1: VNSPOJ-TJALG

Lời giải 1 (của Ngọc Mai): Ideone.com

Lời giải 2 (của Nguyễn Tiến Trung Kiên – kc97ble, NUS): kc97ble

 

Bài toán 2: Codeforces 427C – Checkposts

Tóm tắt bài toán: Cho một đồ thị có hướng gồm n đỉnh, m cạnh. Mỗi đỉnh i có một giá trị v(i) cố định. Hãy chọn tập hợp các đỉnh sao cho mỗi đỉnh đại diện cho một TPLTM, và tổng giá trị của các đỉnh được chọn là nhỏ nhất. Đồng thời, cho biết có bao nhiêu cách chọn tập đỉnh thỏa mãn? (2 cách khác nhau khi có bất kỳ 1 phần tử nào khác nhau, đáp số lấy dư khi chia cho 10^9+7).

Phương pháp: Ta sẽ liệt kê tất cả các TPLTM của đồ thị, và với mỗi TPLTM chọn ra 1 giá trị nhỏ nhất. Tổng các giá trị này sẽ là số đầu tiên của output.

Số thứ 2 của output sẽ được tính theo cách: với mỗi TPLTM, ta tìm xem có bao nhiêu đỉnh có giá trị bằng với giá trị min cho TPLTM đó – số cần tìm là tích số lần xuất hiện ở mỗi TPLTM (chú ý chia dư).

Lời giải (của D.Bách): Submission 35816808

 

#ThuyTrang_12A2

Kỹ thuật lan truyền lười nhác (Lazy Propagation) trong cây phân đoạn (Segment Tree)

Khác với nhiều blog khác, mọi số thứ tự của blog này được đếm từ 1.

 

Series về cây phân đoạn (Segment Tree):

• Khái niệm và cài đặt căn bản
• Cập nhật dạng đa thức (polynomial updates) (chưa cập nhật)
• Cây động (Dynamic tree) (chưa cập nhật)

Lần này, ta xét đến bài toán có dạng sau:

Cho một mảng A kích thước N. Thực hiện một số lượng truy vấn như sau:

Mỗi truy vấn thuộc 1 trong 2 dạng:

• Dạng 1: Gồm 3 số nguyên l, r, x (1 <= l, r <= N, 0 <= x <= 10^3). Khi gặp truy vấn dạng này, ta tăng mỗi phần tử ở đoạn [l, r] thêm x đơn vị.
• Dạng 2: Gồm 2 số nguyên l, r. Khi gặp truy vấn dạng này, hãy tìm:
  • Tổng các phần tử trong đoạn [l, r]
  • Giá trị (hoặc chỉ số) của phần tử nhỏ nhất trong đoạn [l, r]
  • Giá trị (hoặc chỉ số) của phần tử lớn nhất trong đoạn [l, r]

Như chúng ta đã đề cập ở blog cơ bản, mỗi một truy vấn cập nhật nếu làm theo phương pháp khờ khạo sẽ có độ phức tạp O(logN) với từng phần tử. Như vậy, mỗi truy vấn dạng 1 sẽ có độ phức tạp ở trường hợp tệ nhất là O(NlogN) – hết sức lớn.

Một trong những phương pháp cải tiến đó là sử dụng kỹ thuật lan truyền lười nhác (Lazy Propagation) trong các truy vấn cập nhật.

Ý tưởng từ sự lười biếng

Thông thường, những người lười có một thói quen thuộc dạng “nước đến chân mới nhảy” – tức là chỉ khi nào cần kíp phải làm một việc gì đó, họ mới bắt tay vào thực hiện.

Ta sẽ áp dụng đúng nguyên lý này cho việc cập nhật mảng qua truy vấn.

Với phương pháp khờ khạo, xuất phát từ nút gốc (nút 1), ta sẽ lan truyền cho tới khi gặp nút lá – đây chính là nguyên nhân kéo dài thời gian mỗi truy vấn cập nhật.

Ở kỹ thuật Lazy Propagation, ta sẽ không thực hiện như vậy, mà sẽ làm tương tự như đối với các truy vấn.

Nguyên tắc của chúng ta sẽ là: nếu nút đang duyệt còn có giá trị được thêm vào chưa xét đến (từ các truy vấn cập nhật xảy ra trước đó, mà do lười biếng nên chưa cập nhật hết), ta buộc phải cập nhật nó trước khi tiếp tục duyệt sâu hơn.

Nguyên lý hoạt động

• Đầu tiên, ta phải thay đổi về kiến trúc của ST. Ở ST lúc này, mỗi nút sẽ không chỉ chứa 1 tham số mà sẽ là 2 tham số:
  • Tham số cơ bản, như thường lệ, chứa giá trị của khoảng cần lưu trữ.
  • Tham số thứ cấp, ta tạm gọi là “lazy” (ngầm định bằng 0), có tính tạm thời, dùng để lưu trữ giá trị thay đổi trên mỗi nút – chỉ khi nào ta cần tính toán các khoảng con của khoảng đang xét, ta mới truyền giá trị lazy này xuống các khoảng con và đặt lại lazy của khoảng gốc về 0.
• Trước hết, ta cần tìm tập các khoảng được lưu trữ trên ST. Như đã đề cập ở blog trước, tập này phải thỏa mãn 2 điều kiện:
  • Các khoảng trong tập không trùng khớp nhau và liên tục nhau (hay nói cách khác, nếu sắp xếp các khoảng theo thứ tự từ trước đến sau, sẽ không có bất kỳ vùng nào chồng lên nhau, và tất cả các khoảng nối liền lại tạo thành 1 khoảng liền mạch lớn).
  • Khoảng liền mạch lớn thu được khi xếp các khoảng nhỏ lại (như đã mô tả ở trên) đúng bằng khoảng mà truy vấn yêu cầu.
• Lưu ý khi chạy hàm đệ quy: Nếu như ở khoảng nào ta đang xét, mà giá trị lazy trên nút tương ứng khác 0, tức là ta buộc phải cập nhật cho các khoảng con (mấu chốt là, trước khi duyệt sâu hơn xuống các nút con, thì các nút cha không được phép còn lưu trữ giá trị lazy):
  • Trước hết, giá trị lazy sẽ được cập nhật vào giá trị cơ bản của nút. Việc cập nhật tùy vào mục đích của cây. Giả sử như khoảng đang xét là [a, b]:
    • Nếu cây lưu trữ giá trị tổng phần tử, ta cộng vào giá trị cơ bản của nút một lượng đơn vị bằng (b – a + 1) * lazy.
    • Nếu cây lưu trữ giá trị min/max của các phần tử, ta cộng vào giá trị cơ bản của nút một lượng đơn vị bằng lazy.
  • Nếu nút đang xét không phải nút lá (còn khoảng con), ta truyền giá trị lazy xuống 2 khoảng con.
  • Sau khi bước trên thực hiện xong (hoặc không thực hiện), vì quá trình đã hoàn tất, đặt lại ở nút đang xét giá trị lazy = 0.
• Sau khi tìm xong tập các khoảng, ta xét từng nút đại diện cho từng khoảng. Ta cập nhật giá trị cơ bản trên nút đại diện cho khoảng đó, và nếu đó không phải nút lá, ta cộng thêm vào giá trị lazy của mỗi nút con trực tiếp của nút đang xét một giá trị x, chính là giá trị cộng thêm cho mỗi phần tử được quy định trên truy vấn.

Ví dụ

Ta xét mảng sau: 

Ta sẽ xây dựng được cây phân đoạn lưu trữ tổng giá trị như sau: (lưu ý là ở mỗi nút không phải lá, giá trị bên trái là giá trị cơ bản, giá trị bên phải là giá trị lazy):

Nếu giả sử, ta có một truy vấn yêu cầu tăng mỗi phần tử của đoạn [6, 14] thêm 2.

Quy trình thực hiện truy vấn sẽ như sau:

• Gọi hàm ở nút 1 (khoảng [1, 16]).
  • Do khoảng này không nằm gọn trong khoảng truy vấn, ta duyệt 2 khoảng con:
  • Gọi hàm ở nút 2 (khoảng [1, 8]).
    • Khoảng này cũng không nằm gọn trong truy vấn.
    • Gọi hàm ở nút 4 (khoảng [1, 4]).
      • Khoảng này không thuộc truy vấn nên dừng duyệt, kết thúc hàm.
    • Gọi hàm ở nút 5 (khoảng [5, 8]).
      • Khoảng này không nằm gọn trong truy vấn.
      • Gọi hàm ở nút 10 (khoảng [5, 6]).
        • Khoảng này không nằm gọn trong truy vấn.
        • Gọi hàm ở nút 20 (khoảng [5, 5]).
          • Khoảng này không thuộc truy vấn nên dừng duyệt, kết thúc hàm.
        • Gọi hàm ở nút 21 (khoảng [6, 6]).
          • Khoảng này nằm gọn ở truy vấn, và là nút lá nên ta chỉ đơn thuần cộng thêm 2 vào giá trị của nút. Giá trị nút lúc này bằng 9.
        • Tổng hợp giá trị cho nút 10: 2 + 9 = 11.
      • Gọi hàm ở nút 11 (khoảng [7, 8]).
        • Khoảng này nằm gọn ở truy vấn, và không phải nút lá nên ta cộng thêm 2 vào giá trị lazy của 2 nút con (22 và 23). Giá trị cơ bản của nút gốc cộng thêm (2 * (8 – 7 + 1) = 4). Nói cách khác, giá trị nút lúc này bằng (8 + 4 = ) 12.
      • Tổng hợp giá trị cho nút 5: 11 + 12 = 23.
    • Tổng hợp giá trị cho nút 2: 22 + 23 = 45.
  • Gọi hàm ở nút 3 (khoảng [9, 16]).
    • Khoảng này không nằm gọn trong truy vấn.
    • Gọi hàm ở nút 6 (khoảng [9, 12]).
      • Khoảng này nằm gọn ở truy vấn, và không phải nút lá nên ta cộng thêm 2 vào giá trị lazy của 2 nút con (12 và 13). Giá trị cơ bản của nút gốc cộng thêm (2 * (12 – 9 + 1) = 8). Nói cách khác, giá trị nút lúc này bằng (20 + 8 = ) 28.
    • Gọi hàm ở nút 7 (khoảng [13, 16]).
      • Khoảng này không nằm gọn trong truy vấn.
      • Gọi hàm ở nút 14 (khoảng [13, 14]).
        • Khoảng này nằm gọn ở truy vấn, và không phải nút lá nên ta cộng thêm 2 vào giá trị lazy của 2 nút con (28 và 29). Giá trị cơ bản của nút gốc cộng thêm (2 * (14 – 13 + 1) = 4). Nói cách khác, giá trị nút lúc này bằng (8 + 4 = ) 12.
      • Gọi hàm ở nút 15 (khoảng [15, 16]).
        • Khoảng này không thuộc truy vấn nên dừng duyệt, kết thúc hàm.
      • Tổng hợp giá trị cho nút 7: 12 + 5 = 17.
    • Tổng hợp giá trị cho nút 3: 28 + 17 = 45.
  • Tổng hợp giá trị cho nút 1: 45 + 45 = 90.

Cây phân đoạn cho tới khi kết thúc xử lý truy vấn này sẽ trở thành như sau:

Ta sẽ thấy ứng dụng của việc sử dụng Lazy Propagation khi thực hiện một truy vấn tìm kiếm ngay sau nó. Giả sử ta cần tìm tổng các phần tử của đoạn [11, 14].

Quá trình thực hiện duyệt đệ quy sẽ diễn ra tương tự. Lúc này ta xét khoảng [11, 12] (nút 13 của cây) và khoảng [13, 14] (nút 14 của cây).

• Ở khoảng [11, 12], do còn giá trị lazy nên ta sẽ tính lại giá trị cơ bản:
  • Giá trị cơ bản lúc này sẽ bằng: basic + lazy * (12 – 11 + 1). Hay cụ thể hơn, giá trị đó sẽ trở thành: 12 + 2 * (12 – 11 + 1) = 16.
  • Do nút 13 không phải nút lá nên 2 nút con tương ứng (26 và 27) sẽ nhận thêm 2 đơn vị vào giá trị lazy trước khi lazy của nút 13 được đặt lại về 0.
• Ở khoảng [13, 14], do không còn giá trị lazy nên ta lấy trực tiếp giá trị cơ bản.
• Tổng hợp kết quả, ta có kết quả truy vấn yêu cầu sẽ là: 16 + 12 = 28.

Rõ ràng, việc lười nhác trong tính toán ở đây không làm phép tính chậm đi, mà ngược lại còn làm quá trình tính toán nhanh hơn rất nhiều nhờ việc bỏ bớt rất nhiều thao tác duyệt lặp lại.

Xét một cách tổng quan, truy vấn cập nhật cũng duyệt theo phương pháp tương đương với các truy vấn trả kết quả: chỉ tìm tập hợp các khoảng liên tục bao trọn toàn bộ khoảng truy vấn yêu cầu, xuất phát tìm kiếm từ nút gốc (nút 1).

Như đã chứng minh ở blog cơ bản, độ phức tạp của một truy vấn dạng này là O(logN).

 

Bài tập code: VNSPOJ-QMAX2

Tóm tắt đề bài:

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].

Input đảm bảo giá trị của mọi phần tử trong A không vượt quá 2^31 – 1.

Code mẫu: Ideone

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

Cấu trúc dữ liệu cây phân đoạn (Segment Tree)

Khác với nhiều blog khác, mọi số thứ tự của blog này được đếm từ 1.

Tưởng tượng như ta phải xử lý một vấn đề sau:

Cho một mảng A. Thực hiện một số lượng truy vấn như sau:

Mỗi truy vấn gồm 2 số (l, r) (1 <= l, r <= A.length). Hãy tìm:

• Tổng các phần tử trong đoạn [l, r]
• Giá trị (hoặc chỉ số) của phần tử nhỏ nhất trong đoạn [l, r]
• Giá trị (hoặc chỉ số) của phần tử lớn nhất trong đoạn [l, r]

Với ý đầu tiên, ta có thể dễ dàng xử lý bằng mảng cộng dồn. Nhưng với các truy vấn tìm max/min lại không hề đơn giản như vậy.

Để khắc phục những nhược điểm của việc tổ chức dữ liệu tuyến tính thông thường, Segment Tree (cây phân đoạn / ST) là một cấu trúc dữ liệu được lựa chọn.

Ưu điểm của ST là có tính tổng quát, có thể giải quyết nhiều dạng truy vấn khác nhau liên quan đến mảng – tuy nhiên, nhược điểm chính của nó là dữ liệu cần sử dụng lớn hơn một số cấu trúc dữ liệu khác (như Interval Tree, Fenwick tree, etc.), và đôi khi việc cài đặt ST cũng không đơn giản.

Xây dựng ST từ array

Cách phổ biến nhất để xây dựng ST từ array dựa trên cảm hứng của cây nhị phân đầy đủ.

Hay nói một cách khác, với một khoảng [x, y] cho trước (x < y), ta luôn có thể chia nó thành 2 khoảng con: [x, floor((x+y)/2)] và [floor((x+y)/2)+1, y] (floor(z) là hàm chỉ phần nguyên của số thực z).

Từ đó, với một mảng A có kích thước N, ta có phương hướng cài đặt ST như sau:

Nút đầu tiên của cây, có số thứ tự 1, lưu trữ thông tin cho khoảng [1, N].

Nút thứ hai của cây, có số thứ tự 2, lưu trữ thông tin cho khoảng [1, floor((1+N)/2)] (khoảng con phía bên trái của khoảng [1, N]).

Nút thứ ba của cây, có số thứ tự 3, lưu trữ thông tin cho khoảng [floor((1+N)/2)+1, N] (khoảng con phía bên phải của khoảng [1, N]).

…

và cứ tiếp tục như vậy.

Tất cả thỏa mãn một số điều kiện:

• Nút thứ nhất (số thứ tự 1) của cây luôn lưu trữ thông tin của toàn bộ mảng.
• Nút lá sẽ luôn lưu trữ thông tin của một phần tử (hay khoảng [x, x]).
• Với mỗi nút khác nút lá có số thứ tự a, lưu trữ thông tin khoảng [x, y]:
  • Nút (2*a) lưu trữ thông tin của khoảng [x, floor((x+y)/2)], tức khoảng con bên trái của khoảng [x, y].
  • Nút (2*a+1) lưu trữ thông tin của khoảng [floor((x+y)/2)+1, y], tức khoảng con bên phải của khoảng [x, y].

Ví dụ với mảng sau: , thì cây phân đoạn tương ứng sẽ như sau, giả sử như ta đang lưu thông tin về tổng các phần tử trong khoảng:

Với phương pháp cài đặt này, có thể khẳng định chắc chắn là kích thước của mảng biểu diễn các nút của cây phân đoạn sẽ không vượt quá 4N.

Nên nhớ rằng, cây phân đoạn ta đang cài đặt dựa trên cảm hứng của cây nhị phân đầy đủ – một cây như vậy luôn có số lượng nút lá ở dạng 2^x. (với x là một số nguyên không âm bất kỳ). Từ đó, dễ dàng thấy được, toàn bộ cây sẽ có 2^(x+1) – 1 nút.

Nhưng để mọi khoảng-1-phần-tử đều được lưu trữ, số nút lá bắt buộc phải không nhỏ hơn số phần tử trong mảng.

Nói cách khác, với phương thức cài đặt tối ưu nhất, x là số nguyên không âm nhỏ nhất thỏa mãn 2^x >= N.

Nếu N có dạng 2^a + b (với a >= 0 và b > 0, nhưng b rất nhỏ), thì tỷ lệ (2^x)/N sẽ rất lớn, tiến dần bằng 2 khi a tiến tới vô cùng và b tiến tới 1.

Hay nói cách khác, khi tiến tới vô cùng: số nút lá sẽ tiến dần tới 2N.

Và tương ứng, số nút trên toàn bộ cây sẽ tiến dần tới 4N.

Tham khảo thêm các cách chứng minh khác tại đây: Codeforces – Blog entry 49939.

Phương pháp xây dựng đã có, bây giờ viết code cài đặt segment tree thế nào?

Ta có thể dễ dàng thực hiện điều này bằng 1 hàm đệ quy: ta sẽ đi từ gốc của cây (nút 1), và truyền dẫn dần xuống theo độ sâu của cây. Hàm đệ quy sẽ chỉ dừng lại khi gặp nút lá: lúc này ta sẽ gán giá trị của phần tử trong mảng tương ứng với khoảng mà nút lá đó được quy ước.

Sau khi đã tìm tới nút lá, ta bắt đầu quay trở về và tính toán các giá trị cho nút cao hơn. Việc tính toán phụ thuộc vào mục đích của cây: nếu tính tổng thì lấy tổng 2 nút con, nếu tìm min/max thì lấy min/max 2 nút con.

Tóm lại, hàm đệ quy này dựa theo tư tưởng chia để trị, xuất phát từ gốc (nút 1), và gồm các quá trình sau:

• Nếu nút là lá (tức khoảng [x, y] được quy ước thỏa mãn x = y):
  • Gán giá trị của nút đúng bằng giá trị của phần tử thứ x trong mảng A.
  • Nếu điều kiện không thỏa mãn thì ta bỏ qua nút này, ngược lại kết thúc lần chạy hàm tại nút này ngay lập tức.
• Nếu hàm chưa thoát ra (không phải lá), thực hiện gọi hàm đệ quy:
  • Lần gọi 1 với nút con bên trái (2*node).
  • Lần gọi 2 với nút con bên phải (2*node+1).
  • Sau 2 lần gọi, tổng hợp kết quả vào nút hiện tại (lấy tổng, min, max, etc.)

Do ST được tạo theo kiến trúc cây nhị phân đầy đủ, nên đường đi từ nút gốc tới mỗi nút lá sẽ chỉ tiêu tốn log2(N) bước gọi hàm mới. Do đó, độ phức tạp cho quá trình khởi tạo cây phân đoạn là O(N*logN).

Trả về giá trị truy vấn

Tới đây là bước quan trọng nhất của bài toán: trả lời các truy vấn tìm min/max/tổng như thế nào?

Chúng ta quay trở lại mảng ở trên: A[] = {5, 8, 6, 3, 2, 7, 2, 6}

Giả sử truy vấn của chúng ta yêu cầu tổng các phần tử trong khoảng [3, 8].

Dễ dàng tính được bằng Số học đơn thuần: sumq(3,8) = 6 + 3 + 2 + 7 + 2 + 6 = 26.

Trong trường hợp xử lý bằng cây nhị phân, ta thực hiện việc tính toán bằng cách: tìm tập các khoảng trong mảng thỏa mãn 2 điều kiện sau:

• Các khoảng trong tập không trùng khớp nhau và liên tục nhau (hay nói cách khác, nếu sắp xếp các khoảng theo thứ tự từ trước đến sau, sẽ không có bất kỳ vùng nào chồng lên nhau, và tất cả các khoảng nối liền lại tạo thành 1 khoảng liền mạch lớn).
• Khoảng liền mạch lớn thu được khi xếp các khoảng nhỏ lại (như đã mô tả ở trên) đúng bằng khoảng mà truy vấn yêu cầu.

Từ đây, ta nhận thấy, để thực hiện việc tính toán, ta có thể sử dụng một hàm đệ quy, gần tương tự như hàm đệ quy ở phần cài đặt ST.

Ý tưởng của hàm đệ quy lần này như sau:

• Lần gọi gốc bắt đầu từ nút gốc (nút 1).
• Nếu khoảng [L, R] lưu trữ trong nút nằm gọn trong khoảng [x, y] của truy vấn (tức là, x <= L <= R <= y), ta trả về giá trị đúng bằng giá trị lưu trên nút và kết thúc lần chạy hàm.
• Nếu không, ta thực hiện gọi xuống 2 khoảng con:
  • Lần gọi 1 với nút con bên trái (2*node).
  • Lần gọi 2 với nút con bên phải (2*node+1).
  • Sau 2 lần gọi. Tổng hợp kết quả và trả về giá trị (tổng/min/max thu được sau 2 lượt gọi khoảng con, phép xử lý tùy thuộc đề bài).

Hãy áp dụng thử với truy vấn tổng phần tử khoảng [3, 8] của mảng A trên.

Thứ tự các bước thực hiện như sau:

• Gọi hàm ở nút 1 (khoảng [1, 8]).
  • Do khoảng này không nằm gọn trong khoảng truy vấn, ta duyệt 2 khoảng con:
  • Gọi hàm ở nút 2 (khoảng [1, 4]).
    • Khoảng này cũng không nằm gọn trong truy vấn.
    • Gọi hàm ở nút 4 (khoảng [1, 2]).
      • Khoảng này không thuộc truy vấn nên dừng duyệt, kết thúc hàm và trả về giá trị 0.
    • Gọi hàm ở nút 5 (khoảng [3, 4]).
      • Khoảng này nằm gọn trong truy vấn, trả về giá trị 9, kết thúc hàm.
    • Tổng hợp kết quả: trả về giá trị (0 + 9 = ) 9.
  • Gọi hàm ở nút 3 (khoảng [5, 8]).
    • Khoảng này nằm gọn trong truy vấn, trả về giá trị 17, kết thúc hàm.
  • Tổng hợp kết quả: trả về giá trị (9 + 17 = ) 26.
  • Kết thúc hàm.

Như vậy, ta cũng thu được kết quả là 26.

Ta thấy rằng, mỗi khoảng được yêu cầu trên truy vấn là mảng liên tục, cộng thêm việc ta duyệt đệ quy từ đỉnh gốc (chứa khoảng lớn nhất) xuống, nên với mỗi tầng của cây phân đoạn, ta chỉ sử dụng tối đa 2 nút ở tầng đó. Do đó, độ phức tạp cho 1 truy vấn là O(logN).

Cập nhật ST (cơ bản)

Nếu giả sử có sự thay đổi ở một phần tử nào đó của cây, ta cũng phải cập nhật lại giá trị đó.

Ở mức độ cơ bản (và có thể coi là khờ khạo), mỗi thao tác được thực hiện tương tự như các thao tác ở các phần trước:

• Gọi hàm đệ quy từ nút gốc (nút 1).
• Truy vấn xuống cho tới khi nào tới nút lá đại diện cho vị trí phần tử cần cập nhật.
• Cập nhật giá trị nút lá và kết thúc hàm đệ quy tại nút lá.
• Trở về tổng hợp giá trị của các khoảng cha. Hay nói cách khác, cập nhật lại giá trị của các nút đại diện cho các khoảng này (tính lại tổng, so sánh giữa 2 khoảng con để cập nhật giá trị max/min mới, etc.).

Mỗi thao tác cập nhật này sẽ có độ phức tạp O(logN). Dĩ nhiên vấn đề sẽ trở nên rắc rối khi ta phải cập nhật một khoảng phần tử cùng lúc…

To be continued…

 

Xem thêm series về các cải tiến / dạng nâng cao của Segment Tree:

• Lazy Propagation
• Cập nhật dạng đa thức (polynomial updates) (chưa cập nhật)
• Cây động (Dynamic tree) (chưa cập nhật)

Bài toán tham khảo 1: VNSPOJ-QMAX

Ta nhận thấy rằng: tất cả các truy vấn làm thay đổi mảng đều diễn ra trước khi các truy vấn yêu cầu tìm giá trị lớn nhất của các khoảng, cho nên dù có thể không phải tối ưu nhất, nhưng với mục đích luyện tập thì ta cũng có thể cài đặt cây phân đoạn ở bài này. Quá trình làm bài này sẽ gồm 2 bước:

• Xây dựng mảng A ban đầu. Độ phức tạp của quá trình này sẽ là O(n+m).
  • Để đạt được độ phức tạp này, ta sử dụng phương pháp mảng cộng dồn.
  • Với phương pháp này, ở mỗi truy vấn yêu cầu tăng tất cả các phần tử ở đoạn [u, v] lên k đơn vị, ta chỉ cần tăng A[u] lên k đơn vị và giảm A[v+1] (nếu có) đi k đơn vị.
  • Sau khi xử lý các truy vấn, ta thực hiện cộng dồn thông qua duyệt tuyến tính từ phần tử thứ 2 trở đi: A[i] += A[i-1] (i > 1).
• Cài đặt cây phân đoạn và trả lời các truy vấn tìm max.
  • Độ phức tạp cho quá trình cài đặt cây là O(n*log n).
  • Độ phức tạp cho việc trả lời các truy vấn là O(q*log n).

Lời giải: Ideone.com

 

Bài toán tham khảo 2: Codeforces 920F – SUM and REPLACE

Tóm tắt bài toán:

Cho một mảng a gồm n (n <= 3*10^5) số nguyên dương, giá trị không vượt quá 10^6. Thực hiện m truy vấn (m <= 3*10^5) thuộc 2 loại:

• Loại 1: REPLACE l r – thay tất cả các phần tử trong đoạn [l, r] từ giá trị x trở thành giá trị D(x), với D(z) là số ước nguyên dương của một số nguyên z.
• Loại 2: SUM l r – tính tổng các phần tử trong đoạn [l, r].

Với mỗi truy vấn loại 2, in ra tổng tìm được.

Phương pháp: Ta dễ dàng rút ra một số nhận xét sau:

• Cây phân đoạn là một cấu trúc thích hợp để giải bài toán này.
• Ta có thể hoàn toàn khởi tạo trước mảng tính D(x) (với 1 <= x <= 10^6) thông qua kỹ thuật sàng nguyên tố Eratosthenes.
• Mỗi số nguyên x (1 <= x <= 10^6) có thể được biến đổi theo hệ thức x := D(x) tối đa (log x) lần cho tới khi x và D(x) bằng nhau (ta tạm gọi một số x thỏa mãn x = D(x) là một số thuộc trạng thái Z).

Với nhận xét thứ 3, làm thế nào để ta tận dụng nó và rút ngắn thời gian thực hiện bài toán? (nhớ rằng, mỗi truy vấn loại 1 có độ phức tạp tối đa là O(N*logN))

Cách 1 (của D. Bách):

Ngoài cây phân đoạn ban đầu dùng để lưu tổng các phần tử của mảng, ta sử dụng thêm 1 cây phân đoạn lưu tổng nữa, nhưng là tổng số lượng phần tử trong khoảng thuộc trạng thái Z.

Mỗi khi cập nhật một phần tử bất kỳ, ta kiểm tra lại phần tử đó ngay lập tức. Nếu sau khi cập nhật nó đã thỏa mãn D(x) = x, tức là phần tử đó thuộc trạng thái Z, và giá trị của các nút đại diện cho khoảng chứa phần tử này sẽ đều tăng thêm 1.

Sau này, khi duyệt các truy vấn cập nhật, ta sẽ thấy: có những lần duyệt sẽ xảy ra ở các khoảng mà toàn bộ các phần tử trong đó đã thuộc trạng thái Z. Lúc này, ta có thể quyết định dừng duyệt tiếp hay không, thông qua một bước kiểm tra đơn giản: tính tổng số phần tử thuộc trạng thái Z thông qua ST thứ hai, nếu giá trị thu được đúng bằng kích thước khoảng thì ta ngừng duyệt tiếp và kết thúc hàm đệ quy ở điểm đó.

Truy vấn tính tổng ta thực hiện như bình thường.

Độ phức tạp của thuật toán là O(m*(log n)^2).

Lời giải: Submission 35221937

Cách 2 (của liv1n9):

Ta nhận thấy rằng: D(x) = x khi và chỉ khi 1 <= x <= 2.

Do đó, ta có thể lập cây phân đoạn thứ hai: cây này lưu giá trị max của các khoảng.

Ở đây, điều kiện dừng cập nhật sẽ dễ hiểu hơn nhiều: nếu giá trị max của khoảng đó không vượt quá 2 thì ta ngừng duyệt (vì chắc chắn mọi phần tử x lúc đó đều thỏa mãn hệ thức D(x) = x, theo nhận xét ở trên).

Truy vấn tính tổng ta thực hiện như bình thường.

Độ phức tạp của thuật toán là O(m*(log n)^2).

Lời giải: Submission 34870782

 

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

Kỹ thuật Hashing trong xử lý xâu

Đây là một bài viết chung về kỹ thuật hashing trong xử lý xâu, không đơn thuần là một bài viết về việc sử dụng hashing cho bài toán so khớp chuỗi.

 

Về các phương pháp khác cho bài toán so khớp chuỗi, xem thêm:

• Sơ lược về bài toán so khớp chuỗi
• Thuật toán Knuth-Morris-Pratt (KMP)
• Thuật toán Z

Hashing là một kỹ thuật có hiệu quả kể cả trong thực tế và trong lập trình thi đấu (competitive programming). Sự hiệu quả của nó nằm ở tốc độ thực thi, sự linh động trong ứng dụng, và khả năng cài đặt vô cùng đơn giản.

Trước hết, để xử lý được một xâu bằng hashing, ta cần có bảng giá trị băm (hash values) của các ký tự có trong xâu đó. Thông thường, hash value của mỗi ký tự được lấy trực tiếp từ mã ASCII của ký tự (hoặc có thể rút gọn hơn, tùy vào giới hạn ký tự có trong xâu).

Ví dụ, với xâu S = “ALLEY”, thì bảng hash values của các ký tự trong xâu này như sau:

Sau khi có bảng hash value cho từng ký tự, ta sẽ tính hash value cho cả xâu. Một trong những phương pháp tính hash value thông dụng nhất, và sẽ được Trang sử dụng ở bài viết này, đó là polynomial hashing (băm đa thức).

Công thức cho giá trị băm theo polynomial hashing với một xâu S độ dài n bất kỳ là:

(S[0]*A^(n-1) + S[1]*A^(n-2) + … + S[n-1]*A^0) mod B

với A, B là các hằng số nguyên cho sẵn, S[0] tới S[n-1] là hash value đã khởi tạo cho các ký tự tương ứng từ 0 tới n-1 của xâu S.

Với A = 3 và B = 97, giá trị băm của xâu S sẽ là:

(65 * 3^4 + 76 * 3^3 + 76 * 3^2 + 69 * 3^1 + 89 * 3^0) mod 97 = 52.

Hai xâu có giá trị băm bằng nhau sẽ được coi là giống nhau.

Ở đây, ta tiến tới một vấn đề quan trọng trong kỹ thuật hashing: xung đột (collision).

Ta nhận thấy, như ở trên đã đề cập, 2 xâu giống nhau sẽ có giá trị băm giống nhau.

Tuy nhiên, giá trị băm của một xâu theo hệ thức ở trên không được tính tuyệt đối:

• Nó phụ thuộc vào giá trị A (điều này có thể dễ dàng xử lý bằng cách chọn A lớn hơn giá trị lớn nhất có thể có của S[i]).
• Việc sử dụng phép modulo với B.
  • Ta thấy rằng, với các xâu lớn, giá trị băm của xâu sẽ lớn tới những mức độ mà các kiểu dữ liệu số nguyên thông thường không thể xử lý được (kể cả với các ngôn ngữ hỗ trợ như Java/C# (BigInteger) hay Python (built-in integer type) thì việc tính toán với chúng cũng sẽ tiêu tốn rất nhiều thời gian). Vậy nên việc xuất hiện giá trị B và phép modulo là bắt buộc.
  • Khi sử dụng phép modulo cho B, tức là ta đã phải chấp nhận một mệnh đề sai: “Nếu x = y thì x mod B = y mod B và ngược lại”. Chiều xuôi của mệnh đề hiển nhiên đúng, nhưng chiều ngược có thể dễ dàng tìm ví dụ để chứng minh sai (chẳng hạn như x = 2, y = 5, B = 3).

Vậy nên, để khả năng xung đột là nhỏ nhất có thể, ngoài việc tối ưu A, ta còn cần phải chọn giá trị B lớn và có ít ước nguyên (thông thường nên chọn B là số nguyên tố) để đảm bảo 2 yếu tố:

• B lớn giúp phổ modulo được rộng
• B ít ước (đặc biệt là B nguyên tố) khiến cho modulo được phân bố đều, và các giá trị khi lấy modulo cho B không bị tụ vào một tập điểm con thực nhất định (khiến một số giá trị z < B không bao giờ xuất hiện sau quá trình băm).

Đối với lập trình thi đấu tại các trang thi có chức năng “hack” (sinh input trong vùng cho phép nhằm đánh hỏng code của người khác) – chẳng hạn như Topcoder hay Codeforces, việc sử dụng 1 giá trị B duy nhất hết sức nguy hiểm nếu gặp phải những coder kinh nghiệm (bất chấp việc xác suất xảy ra collision rất nhỏ, nhưng các input để thử code có thể được viết bằng tay, và các coder đủ kinh nghiệm hoàn toàn có thể biết các test “chết” để đánh hỏng các code sử dụng hashing).

Một trong những cách khắc phục đơn giản nhất là sử dụng nhiều giá trị B khác nhau và thực hiện băm đồng thời chúng.

Quy tắc so khớp ở đây sẽ là:

Giả sử có N giá trị B khác nhau được dùng làm modulo để thực hiện băm đồng thời. Như vậy, hai xâu sẽ được coi là trùng nhau nếu ở cả N lần băm, giá trị băm của chúng đều bằng nhau.

(Tất nhiên, phương pháp này để giảm thiểu xác suất collision ở một mức độ đáng kể, nhưng không hoàn toàn).

Sau khi xem xét về collisions và các phương pháp cải thiện, ta quay lại mục tiêu chính: tính hash values như thế nào là tối ưu?

Ta quay lại với phương pháp băm đa thức (polynomial hashing) đề cập ở trên. Với phương pháp này, ta có thể tìm hash value cho bất cứ dãy con liên tục nào của xâu S với độ phức tạp O(1), sau khi đã khởi tạo trước bằng một thuật toán với độ phức tạp O(|S|).

Ta sẽ tạo một mảng số nguyên pH[], trong đó pH[i] chứa giá trị băm của tiền tố S[0…i]. Hiển nhiên, pH[0] = S[0]. Với pH[i] (i > 0), ta có công thức truy hồi:

pH[i] = (pH[i-1] * A + S[i]) mod B

Đồng thời, ta lưu thêm một mảng số nguyên pow[] thỏa mãn:

pow[i] = (A ^ i) mod B

Từ đây, bất cứ khi nào ta cần tính giá trị băm của một chuỗi con S[a…b] (a <= b), ta có thể tính toán bằng công thức sau:

(pH[b] – pH[a-1] * pow[b-a+1]) mod B

Độ phức tạp cho quá trình khởi tạo là O(|S|), do việc tính toán theo công thức truy hồi hay tính toán pow[] chỉ đơn giản là một quá trình duyệt tuyến tính.

 

Hashing là một thuật toán đa năng, có thể áp dụng cho nhiều bài toán khác nhau:

Bài toán so khớp chuỗi

Bài toán: Cho 2 xâu A và B. Hãy tìm các vị trí trên xâu A mà nó khớp với xâu B.

Ví dụ: với A = “aaaaa”, B = “aa”, thì các vị trí tìm được là 1, 2, 3, 4 (giả định là ta đang dùng hệ đếm từ 1).

Trước hết, ta giả định xâu A và xâu B của bài toán như sau:

A = “aaaaa”

B = “aa”

Tạm thời coi như A và B chỉ chứa các chữ cái Latin viết thường, vậy nên hệ cơ số của hash value ta sẽ tạm đặt là 26.

Để tránh collision, modulo sẽ được đặt rất cao và là một số nguyên tố. Một giá trị đủ lớn có thể sử dụng mà không lo về tràn số là (1e9 + 7).

Ta coi hash value của 1 ký tự là thứ tự của nó trong bảng chữ cái tiếng Anh (đếm từ 0).

Vậy hiển nhiên, mọi ký tự trong cả 2 xâu đều có hash value là 0.

Từ đó dẫn đến, hash value của B sẽ là: (0 * 26 + 0) mod (1e9 + 7) = 0.

Ta thực hiện duyệt từng dãy con liên tục độ dài |B| của xâu A. Thực tế, xâu nào cũng là “aa” (và theo công thức, hash value luôn là: (0 * 26 + 0) mod (1e9 + 7) = 0) nên ta thu được 4 vị trí trùng khớp tương ứng.

Bài tập code: VNSPOJ-SUBSTR

Code mẫu (1 module): Ideone.com

Code mẫu (đa modules): Ideone.com

 

To be continued….

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

Tham khảo từ bài viết về Hashing tại VNOI.

#ThuyTrang_12A2