Piau 的筆記本

Binary-Search 二分搜尋法的觀念我懶得寫了 這篇筆記主要是當初學習二分搜尋法時 看著那 10 行不到的程式碼，就覺得看一下就會了 結果當要實際寫程式碼時，怎麼寫怎麼錯 因此決定把區間的維護方式記錄在我的筆記中 偽代碼 根據區間定義不同 程式碼會更動的地方 12345678910int binary_search(vector<int> &v, int target) { int l = 0, r = v.size() - 是否包含; while (區間是否合法) { int mid = l + ((r - l) >> 1); if (v[mid] > target) 縮小右區間; else if (v[mid] < target) 縮小左區間; else return mid; } return -1; } 左閉右閉 [l, r] 初始化 因為左右皆為包含 所以給予正常的索引值即可 1int l = 0, r =...

Union-Find (Disjoint-Set) 從 Disjoint-Set (DSU) 這個名字來看 這個資料結構是由許多 Set（集合） 所組成，並且彼此 Disjoint（互斥） 通常會用來解決 集合合併 和 集合查找 的問題 要點 功能 union：合併，將兩個集合合併為一個集合 find：查找某節點的根節點，用來確定該節點屬於哪一個集合 可以針對其他的需求實作 例如：size（查詢集合中有幾項元素）、sum（查詢集合的數值總和） 觀念 需要一個一維陣列用來記錄各個節點的父節點 初始化時，每個節點的父節點都是自己或是原本已指定好的圖 在隨著多次合併之後，可以利用遞迴函式查找到 a 和 b 節點的根節點來判斷是否在同一個集合內 實作細節 find 這邊除了直接查找根節點之外，同時還用了一種觀念就是 「路徑壓縮」 路徑壓縮也就是在查詢的過程中順便將所有經過的節點指向根節點，使其扁平化 1int Find(int x) { return (anc[x] == x ? x : anc[x] = Find(anc[x])); } union 如果 p 的根節點與 q...

Topological-Sorting（拓樸排序） 拓樸排序是 只有祖先都被走訪過的節點 才能被走訪 通常會在有向圖中的邊，用來陳述 A, B 的優先性 也就是當 A → B 時，代表 A 先被走訪後才能走訪 B 要點 觀念 此演算法需要 一維陣列：儲存某節點的未訪問祖先數量 二維陣列：儲存圖（鄰接串列） 佇列：儲存祖先已走訪完畢的節點（用佇列保持其順序性） 先找到沒有父節點的節點作為起始節點 (x) 將其放入佇列中 對所有 x → ? 的 ? 節點，將其一維陣列減 1 同時檢查，若 ? 節點的祖先已全部走訪完畢，則將 ? 放入佇列中 本文默認輸入的有向圖圍為單連通 若想要檢查該圖是否存在環，可以檢查拓樸排序的輸出有無包含所有節點 實作 宣告陣列 一維陣列 (w) 二維陣列 (g) 123// n 為節點數量 vector<vector<int>> g(n); vector<int> w(n, 0); 路徑數量 圖以鄰接串列的方式儲存 設某節點的未走訪父節點為該節點的權重 123456// m 為路徑數量 while (m--) { ...

Fenwick Tree 相較於前綴和只能用來查詢區間和 當我們想要修改某項數值時，就需要重新處理一次 前綴和的 O(1) 求區間和，無法滿足大量的修改操作 這時候可以使用 Fenwick Tree 來快速的修改、求總和 Fenwick Tree 可以在 O(n) 的時間初始化，並且在 O(log n) 的時間查詢區間和、修改其中一項元素的值 別名：Binary Indexed Tree、BIT、樹狀數組 要點 功能 update：更新某項元素的值 query：查詢某範圍的區間和 lowbit lowbit 是整個資料結構的核心 假如 n = ，那 n 的二進制表示法就是 這時候 n 可以拆分成 + ，則 n 的 lowbit 就是 （取最小的位元） 從二進制上可以直接理解為 10010 的 lowbit 是 10 觀念 我們會需要兩個一維陣列 v 跟 bit v：原數列 BIT：預處理後的數列 最後可以藉由 bit 陣列求出前綴和並計算該區間和 因為位元計算 lowbit 及前綴求區間和，BIT 陣列也是 1-based 底下是 BIT 的圖解 圖片引用自...

前綴和 前綴和是對於數列的一種預處理 經過 O(n) 初始化過後可以在 O(1) 就取得 [a, b] 的區間和 一維前綴和 要點 功能 query：查詢某範圍的區間和 觀念 一維前綴和就是將第 N 項的數字改為 N 之前的所有總和 之後每次進行查詢我們就只需要輸出第 b 項數字減去第 a - 1 項數字 為了避免 a - 1 會減到負數 我們需要將索引改成 1-based，並將第 0 項數字設為 0 實作 陣列宣告 1vector<int> v(n+1, 0); 資料輸入 1234for (int i = 1; i <= n; i++) { cin >> v[i]; v[i] += v[i-1]; } 查詢 12cin >> a >> b; cout << v[b] - v[a-1]; 二維前綴和 要點 v[i][j] 儲存左上 ( 0, 0 ) 右下 (i, j) 內的總和 剩下的交給圖來解釋 圖片引用自...