並查集的路徑壓縮：並查集優化，讓查找更快
並查集用於解決集合合併與元素歸屬問題（如連通性判斷）。核心操作是`find`（查找根節點）和`union`（合併集合），基礎版通過`parent`數組記錄父節點實現，但長鏈結構會導致`find`效率極低。爲優化，引入**路徑壓縮**：在`find`過程中，將路徑上所有節點直接指向根節點，使樹結構扁平化，查找效率接近O(1)。路徑壓縮通過遞歸或迭代實現，將長鏈轉化爲“一步到位”的短路徑。結合按秩合併等優化，可高效處理大規模集合問題，成爲解決連通性、歸屬判斷的核心工具。
閱讀全文前綴和：前綴和數組如何快速計算區間和？
前綴和數組是一種用於快速計算區間和的輔助數組。定義爲：原數組A的前綴和數組S，其中S[0]=0，S[k]（k≥1）是A[1]到A[k]的和，即S[k] = S[k-1] + A[k]。例如原數組A=[1,2,3,4,5]，其前綴和數組S=[0,1,3,6,10,15]。 計算區間和的核心公式是：原數組從第i個到第j個元素的和 = S[j] - S[i-1]。例如計算A[2]到A[4]的和，用S[4]-S[1]=10-1=9，結果正確。 優勢在於：預處理S數組需O(n)時間，每次區間和查詢僅需O(1)時間，總複雜度O(n+q)（q爲查詢次數），遠快於直接計算的O(qn)。需注意索引對齊（如原數組從0開始時公式調整）、區間合法性及空間換時間的特點。 前綴和數組通過“提前累積”實現
閱讀全文