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:

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):

cses-fi-bellmanford1

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):

cses-fi-bellmanford2

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:

cses-fi-bellmanford3

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

cses-fi-bellmanford4

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:

cses-fi-bellmanford6

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

 

Advertisements

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:

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):
cses-fi-dijkstra1

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: cses-fi-dijkstra2

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:

cses-fi-dijkstra3

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:

cses-fi-dijkstra4

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:

cses-fi-dijkstra5.png

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:

cses-fi-dijkstra6.png

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:

cses-fi-dijkstra7

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:

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: cses-fi-floyd1

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:

cses-fi-floyd2

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: cses-fi-floyd3.png

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à: cses-fi-floyd4.png

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:

cses-fi-floyd5.png

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: cses-fi-floyd6

 

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): cses-fi-floyd7
  2. Tính toán giá trị đường đi ngắn nhất: cses-fi-floyd8

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):

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: cses-fi-st_lazy1

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):

cses-fi-st_lazy2

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:

cses-fi-st_lazy3

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: cses-fi-st1, 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:

cses-fi-st2

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.

cses-fi-st3

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