# 平方根分解技術 系列 1（簡介） > 原文： [https://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/](https://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/) 平方根（Sqrt）分解技術是競爭程序員使用的最常見的[通用查詢優化技術之一](https://www.geeksforgeeks.org/range-minimum-query-for-static-array/)。 此技術幫助我們將時間復雜度降低`sqrt(n)`。 *該技術的關鍵概念是將給定的數組分解為大小為`sqrt(n)`的小塊。* 假設我們有一個`n`個元素的數組，然后將其分解為大小為`sqrt(n)`的小塊。 如果`n`是一個完美的正方形，我們將恰好具有`sqrt(n)`這樣的塊。 因此，現在我們將`n`個元素上的數組分解為`sqrt(n)`塊，其中每個塊都包含`sqrt(n)`元素（假設數組的大小是完美正方形）。 讓我們將這些塊或塊視為一個單獨的數組，每個數組包含`sqrt(n)`元素，并且您已經針對所有塊分別計算了所需的答案（根據您的問題）。 現在，您需要回答某些查詢，詢問原始`n`大小數組中范圍為`l`到`r`（`l`和`r`是數組的開始和結束索引）的元素的答案。 **樸素的方法**只是簡單地遍歷范圍`l`到`r`中的每個元素，并計算其相應的答案。 因此，每個查詢的時間復雜度將為`O(n)`。 **平方分解技巧**：由于我們已經預先計算了所有單個數據塊的答案，現在我們需要回答范圍`l`到`r`的查詢。 現在，我們可以簡單地組合原始數組中介于`l`到`r`之間的塊的答案。 因此，如果我們在這里仔細觀察，我們將一次跳過`sqrt(n)`步，而不是像樸素的方法那樣一次跳過 1 步。 讓我們考慮以下問題來分析其時間復雜度和實現： ``` Problem : Given an array of n elements. We need to answer q queries telling the sum of elements in range l to r in the array. Also the array is not static i.e the values are changed via some point update query. Range Sum Queries are of form : Q l r , where l is the starting index r is the ending index Point update Query is of form : U idx val, where idx is the index to update val is the updated value ``` 讓我們考慮一下，我們有 9 個元素組成的數組。 `A [] = {1, 5, 2, 4, 6, 1, 3, 5, 7}` 讓我們將此數組分解為`sqrt(9)`塊，其中每個塊將包含其中的元素總和。 因此，現在我們的分解數組將如下所示：  到目前為止，我們已經構造了分解后的`sqrt(9)`塊數組，現在我們需要打印給定范圍內的元素總數。 因此，首先讓我們看一下范圍查詢可以在數組上出現的兩種基本重疊類型： **類型 1 的范圍查詢（給定范圍位于塊邊界上）**：  在這種類型的查詢中，范圍可能完全覆蓋連續的`sqrt`塊。 因此，我們可以輕松地將此范圍內的值之和回答為完全重疊的塊之和。 因此，上述圖像中上述查詢的答案將是：`ans = 11 + 15 = 26` **時間復雜度**：在最壞的情況下，我們的范圍可以是 0 至`n-1`（其中`n`是數組的大小，并假設`n`是一個完美的正方形）。 在這種情況下，我們的查詢范圍將所有塊完全重疊。 因此，要回答此查詢，我們需要遍歷該數組的所有分解塊，并且知道塊數`= sqrt(n)`。 因此，在最壞的情況下，此類查詢的復雜度將為`O(sqrt(n))`。 **類型 2 的范圍查詢（鑒于范圍不在邊界上）**  我們可以通過對位于查詢范圍內的完全重疊的分解塊中的數據求和，然后對來自原始數組的元素進行逐一求和，而原始數組的原始塊的相應塊未與查詢范圍完全重疊，則可以處理此類查詢。 因此，上述圖像中上述查詢的答案將是：`ans = 5 + 2 + 11 + 3 = 21` **時間復雜度**：讓我們考慮一個查詢`[l = 1, r = n-2]`（`n`是數組的大小，并具有從 0 開始的索引）。 因此，對于該查詢，正好`sqrt(n) – 2`塊將完全重疊，其中第一個和最后一個塊將部分重疊，而重疊范圍之外僅剩一個元素。 因此，完全重疊的塊可以在`(sqrt(n) – 2) ~ sqrt(n)`迭代中求和，而第一個塊和最后一個塊需要分別遍歷。 但是我們知道每個塊中的元素數量為最大`sqrt(n)`，所以要單獨求和最后一個塊，我們需要進行`(sqrt(n) - 1) ~ sqrt(n)`個迭代。 因此，總體復雜度`= O(sqrt(n))+ O(sqrt(n))+ O(sqrt(n))= O(3 * sqrt(N))= **O(sqrt( n))` **更新查詢（點更新）**： 在此查詢中，我們僅查找給定索引所在的塊，然后減去其先前的值并根據點更新查詢添加新的更新值。 **時間復雜度**：`O(1)` **實現**： 下面給出了上述技巧的實現 ## C++ ```cpp // C++ program to demonstrate working of Square Root // Decomposition. #include "iostream" #include "math.h" using namespace std; #define MAXN 10000 #define SQRSIZE? 100 int arr[MAXN];?????????????? // original array int block[SQRSIZE];????????? // decomposed array int blk_sz;????????????????????? // block size // Time Complexity : O(1) void update(int idx, int val) { ????int blockNumber = idx / blk_sz; ????block[blockNumber] += val - arr[idx]; ????arr[idx] = val; } // Time Complexity : O(sqrt(n)) int query(int l, int r) { ????int sum = 0; ????while (l<r and l%blk_sz!=0 and l!=0) ????{ ????????// traversing first block in range ????????sum += arr[l]; ????????l++; ????} ????while (l+blk_sz <= r) ????{ ????????// traversing completely overlapped blocks in range ????????sum += block[l/blk_sz]; ????????l += blk_sz; ????} ????while (l<=r) ????{ ????????// traversing last block in range ????????sum += arr[l]; ????????l++; ????} ????return sum; } // Fills values in input[] void preprocess(int input[], int n) { ????// initiating block pointer ????int blk_idx = -1; ????// calculating size of block ????blk_sz = sqrt(n); ????// building the decomposed array ????for (int i=0; i<n; i++) ????{ ????????arr[i] = input[i]; ????????if (i%blk_sz == 0) ????????{ ????????????// entering next block ????????????// incementing block pointer ????????????blk_idx++; ????????} ????????block[blk_idx] += arr[i]; ????} } // Driver code int main() { ????// We have used separate array for input because ????// the purpose of this code is to explain SQRT ????// decomposition in competitive programming where ????// we have multiple inputs. ????int input[] = {1, 5, 2, 4, 6, 1, 3, 5, 7, 10}; ????int n = sizeof(input)/sizeof(input[0]); ????preprocess(input, n); ????cout << "query(3,8) : " << query(3, 8) << endl; ????cout << "query(1,6) : " << query(1, 6) << endl; ????update(8, 0); ????cout << "query(8,8) : " << query(8, 8) << endl; ????return 0; } ```