給定子數組中小于或等于給定數字的元素數| 第 2 組（包括更新） · GeeksForGeeks 中文系列教程

# 給定子數組中小于或等于給定數字的元素數| 第 2 組（包括更新） > 原文： [https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-2-including-updates/](https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-2-including-updates/) 給定數組`a[]`和查詢數量`q`，將有兩種查詢類型 1. **查詢 0 `update(i, v)`**：兩個整數`i`和`v`，表示設置`a[i] = v` 2. **查詢 1 `count(l, r, k)`**：我們需要在子數組`l`至`r`中打印小于等于`k`的整數。給定`a[i]`，`v < = 10000` **示例**： ``` Input : arr[] = {5, 1, 2, 3, 4} q = 6 1 1 3 1 // First value 1 means type of query is count() 0 3 10 // First value 0 means type of query is update() 1 3 3 4 0 2 1 0 0 2 1 0 4 5 Output : 1 0 4 For first query number of values less than equal to 1 in arr[1..3] is 1(1 only), update a[3] = 10 There is no value less than equal to 4 in the a[3..3] and similarly other queries are answered ``` 我們在下面的文章中討論了僅處理`count()`查詢的解決方案。 [在給定子數組](https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/)中小于或等于給定數目的元素數這里`update()`查詢也需要處理。 **樸素方法**樸素方法是只要有更新操作就更新數組，并且只要有類型 2 查詢就遍歷子數組并計算有效元素。 **有效方法** 這個想法是使用[平方根分解](https://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/) 1. **步驟 1**：將數組劃分為`sqrt(n)`個相等大小的塊。對于每個塊，保持二進制索引樹的大小等于該塊中元素數組中最大可能元素的 1。 2. 步驟 2：對于數組中的每個元素，找出其所屬的塊，并使用`arr[i]`處的值 1 更新該塊的位數組。 3. 步驟 3：每當有更新查詢時，將對應塊的位數組更新為該索引處數組的原始值，其值等于 -1，并將同一塊的位數組更新為值 1 的新值。該索引處數組的大小。 4. 步驟 4：對于類型 2 查詢，您可以對范圍中的每個完整塊對位進行單個查詢（以計數小于或等于`k`的元素），最后對于兩個部分塊，只需遍歷這些元素。 ## C++ ```cpp // Number of elements less than or equal to a given // number in a given subarray and allowing update // operations. #include<bits/stdc++.h> using namespace std; const int MAX = 10001; // updating the bit array of a valid block void update(int idx, int blk, int val, int bit[][MAX]) { ????for (; idx<MAX; idx += (idx&-idx)) ????????bit[blk][idx] += val; } // answering the query int query(int l, int r, int k, int arr[], int blk_sz, ??????????????????????????????????????int bit[][MAX]) { ????// traversing the first block in range ????int sum = 0; ????while (l<r && l%blk_sz!=0 && l!=0) ????{ ????????if (arr[l] <= k) ????????????sum++; ????????l++; ????} ????// Traversing completely overlapped blocks in ????// range for such blocks bit array of that block ????// is queried ????while (l + blk_sz <= r) ????{ ????????int idx = k; ????????for (; idx > 0 ; idx -= idx&-idx) ????????????sum += bit[l/blk_sz][idx]; ????????l += blk_sz; ????} ????// Traversing the last block ????while (l <= r) ????{ ????????if (arr[l] <= k) ????????????sum++; ????????l++; ????} ????return sum; } // Preprocessing the array void preprocess(int arr[], int blk_sz, int n, int bit[][MAX]) { ????for (int i=0; i<n; i++) ????????update(arr[i], i/blk_sz, 1, bit); } void preprocessUpdate(int i, int v, int blk_sz, ??????????????????????int arr[], int bit[][MAX]) { ????// updating the bit array at the original ????// and new value of array ????update(arr[i], i/blk_sz, -1, bit); ????update(v, i/blk_sz, 1, bit); ????arr[i] = v; } // driver function int main() { ????int arr[] = {5, 1, 2, 3, 4}; ????int n = sizeof(arr)/sizeof(arr[0]); ????// size of block size will be equal to square root of n ????int blk_sz = sqrt(n); ????// initialising bit array of each block ????// as elements of array cannot exceed 10^4 so size ????// of bit array is accordingly ????int bit[blk_sz+1][MAX]; ????memset(bit, 0, sizeof(bit)); ????preprocess(arr, blk_sz, n, bit); ????cout << query? (1, 3, 1, arr, blk_sz, bit) << endl; ????preprocessUpdate(3, 10, blk_sz, arr, bit); ????cout << query(3, 3, 4, arr, blk_sz, bit) << endl; ????preprocessUpdate(2, 1, blk_sz, arr, bit); ????preprocessUpdate(0, 2, blk_sz, arr, bit); ????cout << query (0, 4, 5, arr, blk_sz, bit) << endl; ????return 0; } ``` ## Java ```java // Number of elements less than or equal to a given // number in a given subarray and allowing update // operations. class Test { ????static final int MAX = 10001; ????// updating the bit array of a valid block ????static void update(int idx, int blk, int val, int bit[][]) ????{ ????????for (; idx<MAX; idx += (idx&-idx)) ????????????bit[blk][idx] += val; ????} ????// answering the query ????static int query(int l, int r, int k, int arr[], int blk_sz, ??????????????????????????????????????????int bit[][]) ????{ ????????// traversing the first block in range ????????int sum = 0; ????????while (l<r && l%blk_sz!=0 && l!=0) ????????{ ????????????if (arr[l] <= k) ????????????????sum++; ????????????l++; ????????} ????????// Traversing completely overlapped blocks in ????????// range for such blocks bit array of that block ????????// is queried ????????while (l + blk_sz <= r) ????????{ ????????????int idx = k; ????????????for (; idx > 0 ; idx -= idx&-idx) ????????????????sum += bit[l/blk_sz][idx]; ????????????l += blk_sz; ????????} ????????// Traversing the last block ????????while (l <= r) ????????{ ????????????if (arr[l] <= k) ????????????????sum++; ????????????l++; ????????} ????????return sum; ????} ????// Preprocessing the array ????static void preprocess(int arr[], int blk_sz, int n, int bit[][]) ????{ ????????for (int i=0; i<n; i++) ????????????update(arr[i], i/blk_sz, 1, bit); ????} ????static void preprocessUpdate(int i, int v, int blk_sz, ??????????????????????????int arr[], int bit[][]) ????{ ????????// updating the bit array at the original ????????// and new value of array ????????update(arr[i], i/blk_sz, -1, bit); ????????update(v, i/blk_sz, 1, bit); ????????arr[i] = v; ????} ????// Driver method ????public static void main(String args[]) ????{ ????????int arr[] = {5, 1, 2, 3, 4}; ????????// size of block size will be equal to square root of n ????????int blk_sz = (int) Math.sqrt(arr.length); ????????// initialising bit array of each block ????????// as elements of array cannot exceed 10^4 so size ????????// of bit array is accordingly ????????int bit[][] = new int[blk_sz+1][MAX]; ????????preprocess(arr, blk_sz, arr.length, bit); ????????System.out.println(query(1, 3, 1, arr, blk_sz, bit)); ????????preprocessUpdate(3, 10, blk_sz, arr, bit); ????????System.out.println(query(3, 3, 4, arr, blk_sz, bit)); ????????preprocessUpdate(2, 1, blk_sz, arr, bit); ????????preprocessUpdate(0, 2, blk_sz, arr, bit); ????????System.out.println(query (0, 4, 5, arr, blk_sz, bit)); ????} } ``` ## Python3 ```py # Number of elements less than or equal to a given # number in a given subarray and allowing update # operations. MAX = 10001 # updating the bit array of a valid block def update(idx, blk, val, bit): ????while idx < MAX: ????????bit[blk][idx] += val ????????idx += (idx & -idx) # answering the query def query(l, r, k, arr, blk_sz, bit): ????# traversing the first block in range ????summ = 0 ????while l < r and l % blk_sz != 0 and l != 0: ????????if arr[l] <= k: ????????????summ += 1 ????????l += 1 ????# Traversing completely overlapped blocks in ????# range for such blocks bit array of that block ????# is queried ????while l + blk_sz <= r: ????????idx = k ????????while idx > 0: ????????????summ += bit[l // blk_sz][idx] ????????????idx -= (idx & -idx) ????????l += blk_sz ????# Traversing the last block ????while l <= r: ????????if arr[l] <= k: ????????????summ += 1 ????????l += 1 ????return summ # Preprocessing the array def preprocess(arr, blk_sz, n, bit): ????for i in range(n): ????????update(arr[i], i // blk_sz, 1, bit) def preprocessUpdate(i, v, blk_sz, arr, bit): ????# updating the bit array at the original ????# and new value of array ????update(arr[i], i // blk_sz, -1, bit) ????update(v, i // blk_sz, 1, bit) ????arr[i] = v # Driver Code if __name__ == "__main__": ????arr = [5, 1, 2, 3, 4] ????n = len(arr) ????# size of block size will be equal? ????# to square root of n ????from math import sqrt ????blk_sz = int(sqrt(n)) ????# initialising bit array of each block ????# as elements of array cannot exceed 10^4? ????# so size of bit array is accordingly ????bit = [[0 for i in range(MAX)]? ??????????????for j in range(blk_sz + 1)] ????preprocess(arr, blk_sz, n, bit) ????print(query(1, 3, 1, arr, blk_sz, bit)) ????preprocessUpdate(3, 10, blk_sz, arr, bit) ????print(query(3, 3, 4, arr, blk_sz, bit)) ????preprocessUpdate(2, 1, blk_sz, arr, bit) ????preprocessUpdate(0, 2, blk_sz, arr, bit) ????print(query(0, 4, 5, arr, blk_sz, bit)) # This code is contributed by # sanjeev2552 ``` ## C# ```cs // Number of elements less than or equal // to a given number in a given subarray // and allowing update operations. using System; class GFG? { ????static int MAX = 10001; ????// updating the bit array of a valid block ????static void update(int idx, int blk,? ????????????????????int val, int [,]bit) ????{ ????????for (; idx < MAX; idx += (idx&-idx)) ????????????bit[blk, idx] += val; ????} ????// answering the query ????static int query(int l, int r, int k, int []arr, ?????????????????????????????int blk_sz, int [,]bit) ????{ ????????// traversing the first block in range ????????int sum = 0; ????????while (l < r && l % blk_sz != 0 && l != 0) ????????{ ????????????if (arr[l] <= k) ????????????????sum++; ????????????l++; ????????} ????????// Traversing completely overlapped blocks in ????????// range for such blocks bit array of that block ????????// is queried ????????while (l + blk_sz <= r) ????????{ ????????????int idx = k; ????????????for (; idx > 0 ; idx -= idx&-idx) ????????????????sum += bit[l/blk_sz,idx]; ????????????l += blk_sz; ????????} ????????// Traversing the last block ????????while (l <= r) ????????{ ????????????if (arr[l] <= k) ????????????????sum++; ????????????l++; ????????} ????????return sum; ????} ????// Preprocessing the array ????static void preprocess(int []arr, int blk_sz, ???????????????????????????????int n, int [,]bit) ????{ ????????for (int i=0; i<n; i++) ????????????update(arr[i], i / blk_sz, 1, bit); ????} ????static void preprocessUpdate(int i, int v, int blk_sz, ????????????????????????????????????int []arr, int [,]bit) ????{ ????????// updating the bit array at the original ????????// and new value of array ????????update(arr[i], i/blk_sz, -1, bit); ????????update(v, i/blk_sz, 1, bit); ????????arr[i] = v; ????} ????// Driver method ????public static void Main() ????{ ????????int []arr = {5, 1, 2, 3, 4}; ????????// size of block size will be? ????????// equal to square root of n ????????int blk_sz = (int) Math.Sqrt(arr.Length); ????????// initialising bit array of each block ????????// as elements of array cannot exceed 10^4 so size ????????// of bit array is accordingly ????????int [,]bit = new int[blk_sz+1,MAX]; ????????preprocess(arr, blk_sz, arr.Length, bit); ????????Console.WriteLine(query(1, 3, 1, arr, blk_sz, bit)); ????????preprocessUpdate(3, 10, blk_sz, arr, bit); ????????Console.WriteLine(query(3, 3, 4, arr, blk_sz, bit)); ????????preprocessUpdate(2, 1, blk_sz, arr, bit); ????????preprocessUpdate(0, 2, blk_sz, arr, bit); ????????Console.WriteLine(query (0, 4, 5, arr, blk_sz, bit)); ????} } // This code is contributed by Sam007 ``` **輸出**： ``` 1 0 4 ``` 問題是知道為什么沒有更新操作時不使用此方法，答案在于使用此方法的空間復雜性 2 維位數組以及其大小取決于數組的最大可能值，但是當存在沒有更新操作，我們的位數組僅取決于數組的大小。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。