배열 arr[0..n-1]이 주어졌습니다. 다음 작업을 수행해야 합니다.
처음에 배열의 모든 요소는 0입니다. 쿼리는 어떤 순서로도 가능합니다. 즉, 포인트 쿼리 전에 많은 업데이트가 있을 수 있습니다.
예:
관계이다
Input: arr = {0 0 0 0 0} Queries: update : l = 0 r = 4 val = 2 getElement : i = 3 update : l = 3 r = 4 val = 3 getElement : i = 3 Output: Element at 3 is 2 Element at 3 is 5 Explanation: Array after first update becomes {2 2 2 2 2} Array after second update becomes {2 2 2 5 5}방법 1 [업데이트 : O(n) getElement() : O(1)]
최악의 경우 시간 복잡도는 O(q*n)입니다. 여기서 q는 쿼리 수이고 n은 요소 수입니다.
방법 2 [업데이트: O(1) getElement(): O(n)]
모든 요소 업데이트를 피할 수 있으며 배열의 인덱스 2개만 업데이트할 수 있습니다!
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
업데이트 쿼리를 분석해 보겠습니다. l에 val을 추가하는 이유일색인? l에 val 추가일index는 모든 요소에 대한 접두사 합계를 계산하므로 l 이후의 모든 요소가 val만큼 증가함을 의미합니다. (r+1)에서 val을 빼는 이유일색인? [lr]에서 범위 업데이트가 필요했지만 업데이트한 내용은 [l n-1]이므로 r 뒤의 모든 요소에서 val을 제거해야 합니다. 즉, (r+1)에서 val을 빼야 합니다.일색인. 따라서 val이 범위 [lr]에 추가됩니다. 아래는 위의 접근 방식을 구현한 것입니다.
C 언어의 rC++
// C++ program to demonstrate Range Update // and Point Queries Without using BIT #include
// Java program to demonstrate Range Update // and Point Queries Without using BIT class GfG { // Updates such that getElement() gets an increased // value when queried from l to r. static void update(int arr[] int l int r int val) { arr[l] += val; if(r + 1 < arr.length) arr[r+1] -= val; } // Get the element indexed at i static int getElement(int arr[] int i) { // To get ith element sum of all the elements // from 0 to i need to be computed int res = 0; for (int j = 0 ; j <= i; j++) res += arr[j]; return res; } // Driver program to test above function public static void main(String[] args) { int arr[] = {0 0 0 0 0}; int n = arr.length; int l = 2 r = 4 val = 2; update(arr l r val); //Find the element at Index 4 int index = 4; System.out.println('Element at index ' + index + ' is ' +getElement(arr index)); l = 0; r = 3; val = 4; update(arrlrval); //Find the element at Index 3 index = 3; System.out.println('Element at index ' + index + ' is ' +getElement(arr index)); } }
# Python3 program to demonstrate Range # Update and PoQueries Without using BIT # Updates such that getElement() gets an # increased value when queried from l to r. def update(arr l r val): arr[l] += val if r + 1 < len(arr): arr[r + 1] -= val # Get the element indexed at i def getElement(arr i): # To get ith element sum of all the elements # from 0 to i need to be computed res = 0 for j in range(i + 1): res += arr[j] return res # Driver Code if __name__ == '__main__': arr = [0 0 0 0 0] n = len(arr) l = 2 r = 4 val = 2 update(arr l r val) # Find the element at Index 4 index = 4 print('Element at index' index 'is' getElement(arr index)) l = 0 r = 3 val = 4 update(arr l r val) # Find the element at Index 3 index = 3 print('Element at index' index 'is' getElement(arr index)) # This code is contributed by PranchalK
// C# program to demonstrate Range Update // and Point Queries Without using BIT using System; class GfG { // Updates such that getElement() // gets an increased value when // queried from l to r. static void update(int []arr int l int r int val) { arr[l] += val; if(r + 1 < arr.Length) arr[r + 1] -= val; } // Get the element indexed at i static int getElement(int []arr int i) { // To get ith element sum of all the elements // from 0 to i need to be computed int res = 0; for (int j = 0 ; j <= i; j++) res += arr[j]; return res; } // Driver code public static void Main(String[] args) { int []arr = {0 0 0 0 0}; int n = arr.Length; int l = 2 r = 4 val = 2; update(arr l r val); //Find the element at Index 4 int index = 4; Console.WriteLine('Element at index ' + index + ' is ' + getElement(arr index)); l = 0; r = 3; val = 4; update(arrlrval); //Find the element at Index 3 index = 3; Console.WriteLine('Element at index ' + index + ' is ' + getElement(arr index)); } } // This code is contributed by PrinciRaj1992
// PHP program to demonstrate Range Update // and Point Queries Without using BIT // Updates such that getElement() gets an // increased value when queried from l to r. function update(&$arr $l $r $val) { $arr[$l] += $val; if($r + 1 < sizeof($arr)) $arr[$r + 1] -= $val; } // Get the element indexed at i function getElement(&$arr $i) { // To get ith element sum of all the elements // from 0 to i need to be computed $res = 0; for ($j = 0 ; $j <= $i; $j++) $res += $arr[$j]; return $res; } // Driver Code $arr = array(0 0 0 0 0); $n = sizeof($arr); $l = 2; $r = 4; $val = 2; update($arr $l $r $val); // Find the element at Index 4 $index = 4; echo('Element at index ' . $index . ' is ' . getElement($arr $index) . 'n'); $l = 0; $r = 3; $val = 4; update($arr $l $r $val); // Find the element at Index 3 $index = 3; echo('Element at index ' . $index . ' is ' . getElement($arr $index)); // This code is contributed by Code_Mech ?> //JavaScript program to demonstrate Range Update // and Point Queries Without using BIT // Updates such that getElement() gets an increased // value when queried from l to r. function update(arr l r val) { arr[l] += val; arr[r+1] -= val; } // Get the element indexed at i function getElement(rr i) { // To get ith element sum of all the elements // from 0 to i need to be computed let res = 0; for (let j = 0 ; j <= i; j++) res += arr[j]; return res; } // Driver program to test above function let arr = [0 0 0 0 0]; let n = arr.length; let l = 2 r = 4 val = 2; update(arr l r val); // Find the element at Index 4 let index = 4; console.log('Element at index 'index' is 'getElement(arr index)); l = 0 r = 3 val = 4; update(arrlrval); // Find the element at Index 3 index = 3; console.log('Element at index 'index' is 'getElement(arr index)); // This code is contributed by vikkycirus
산출:
Element at index 4 is 2 Element at index 3 is 6
시간 복잡도 : O(q*n) 여기서 q는 쿼리 수입니다.
보조 공간: 에)
방법 3(이진 인덱스 트리 사용)
방법 2에서는 문제가 업데이트 및 접두사 합계 쿼리로 줄어들 수 있음을 확인했습니다. 우리는 그것을 보았다 BIT는 O(Logn) 시간에 업데이트 및 접두사 합계 쿼리를 수행하는 데 사용할 수 있습니다. 아래는 구현입니다.
C++// C++ code to demonstrate Range Update and // Point Queries on a Binary Index Tree #include
/* Java code to demonstrate Range Update and * Point Queries on a Binary Index Tree. * This method only works when all array * values are initially 0.*/ class GFG { // Max tree size final static int MAX = 1000; static int BITree[] = new int[MAX]; // Updates a node in Binary Index // Tree (BITree) at given index // in BITree. The given value 'val' // is added to BITree[i] and // all of its ancestors in tree. public static void updateBIT(int n int index int val) { // index in BITree[] is 1 // more than the index in arr[] index = index + 1; // Traverse all ancestors // and add 'val' while (index <= n) { // Add 'val' to current // node of BITree BITree[index] += val; // Update index to that // of parent in update View index += index & (-index); } } // Constructs Binary Indexed Tree // for given array of size n. public static void constructBITree(int arr[] int n) { // Initialize BITree[] as 0 for(int i = 1; i <= n; i++) BITree[i] = 0; // Store the actual values // in BITree[] using update() for(int i = 0; i < n; i++) updateBIT(n i arr[i]); // Uncomment below lines to // see contents of BITree[] // for (int i=1; i<=n; i++) // cout << BITree[i] << ' '; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This // function assumes that the array is // preprocessed and partial sums of // array elements are stored in BITree[] public static int getSum(int index) { int sum = 0; //Initialize result // index in BITree[] is 1 more // than the index in arr[] index = index + 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Add current element // of BITree to sum sum += BITree[index]; // Move index to parent // node in getSum View index -= index & (-index); } // Return the sum return sum; } // Updates such that getElement() // gets an increased value when // queried from l to r. public static void update(int l int r int n int val) { // Increase value at // 'l' by 'val' updateBIT(n l val); // Decrease value at // 'r+1' by 'val' updateBIT(n r + 1 -val); } // Driver Code public static void main(String args[]) { int arr[] = {0 0 0 0 0}; int n = arr.length; constructBITree(arrn); // Add 2 to all the // element from [24] int l = 2 r = 4 val = 2; update(l r n val); int index = 4; System.out.println('Element at index '+ index + ' is '+ getSum(index)); // Add 2 to all the // element from [03] l = 0; r = 3; val = 4; update(l r n val); // Find the element // at Index 3 index = 3; System.out.println('Element at index '+ index + ' is '+ getSum(index)); } } // This code is contributed // by Puneet Kumar.
# Python3 code to demonstrate Range Update and # PoQueries on a Binary Index Tree # Updates a node in Binary Index Tree (BITree) at given index # in BITree. The given value 'val' is added to BITree[i] and # all of its ancestors in tree. def updateBIT(BITree n index val): # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse all ancestors and add 'val' while (index <= n): # Add 'val' to current node of BI Tree BITree[index] += val # Update index to that of parent in update View index += index & (-index) # Constructs and returns a Binary Indexed Tree for given # array of size n. def constructBITree(arr n): # Create and initialize BITree[] as 0 BITree = [0]*(n+1) # Store the actual values in BITree[] using update() for i in range(n): updateBIT(BITree n i arr[i]) return BITree # SERVES THE PURPOSE OF getElement() # Returns sum of arr[0..index]. This function assumes # that the array is preprocessed and partial sums of # array elements are stored in BITree[] def getSum(BITree index): sum = 0 # Initialize result # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse ancestors of BITree[index] while (index > 0): # Add current element of BITree to sum sum += BITree[index] # Move index to parent node in getSum View index -= index & (-index) return sum # Updates such that getElement() gets an increased # value when queried from l to r. def update(BITree l r n val): # Increase value at 'l' by 'val' updateBIT(BITree n l val) # Decrease value at 'r+1' by 'val' updateBIT(BITree n r+1 -val) # Driver code arr = [0 0 0 0 0] n = len(arr) BITree = constructBITree(arr n) # Add 2 to all the element from [24] l = 2 r = 4 val = 2 update(BITree l r n val) # Find the element at Index 4 index = 4 print('Element at index' index 'is' getSum(BITree index)) # Add 2 to all the element from [03] l = 0 r = 3 val = 4 update(BITree l r n val) # Find the element at Index 3 index = 3 print('Element at index' index 'is' getSum(BITreeindex)) # This code is contributed by mohit kumar 29
using System; /* C# code to demonstrate Range Update and * Point Queries on a Binary Index Tree. * This method only works when all array * values are initially 0.*/ public class GFG { // Max tree size public const int MAX = 1000; public static int[] BITree = new int[MAX]; // Updates a node in Binary Index // Tree (BITree) at given index // in BITree. The given value 'val' // is added to BITree[i] and // all of its ancestors in tree. public static void updateBIT(int n int index int val) { // index in BITree[] is 1 // more than the index in arr[] index = index + 1; // Traverse all ancestors // and add 'val' while (index <= n) { // Add 'val' to current // node of BITree BITree[index] += val; // Update index to that // of parent in update View index += index & (-index); } } // Constructs Binary Indexed Tree // for given array of size n. public static void constructBITree(int[] arr int n) { // Initialize BITree[] as 0 for (int i = 1; i <= n; i++) { BITree[i] = 0; } // Store the actual values // in BITree[] using update() for (int i = 0; i < n; i++) { updateBIT(n i arr[i]); } // Uncomment below lines to // see contents of BITree[] // for (int i=1; i<=n; i++) // cout << BITree[i] << ' '; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This // function assumes that the array is // preprocessed and partial sums of // array elements are stored in BITree[] public static int getSum(int index) { int sum = 0; //Initialize result // index in BITree[] is 1 more // than the index in arr[] index = index + 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Add current element // of BITree to sum sum += BITree[index]; // Move index to parent // node in getSum View index -= index & (-index); } // Return the sum return sum; } // Updates such that getElement() // gets an increased value when // queried from l to r. public static void update(int l int r int n int val) { // Increase value at // 'l' by 'val' updateBIT(n l val); // Decrease value at // 'r+1' by 'val' updateBIT(n r + 1 -val); } // Driver Code public static void Main(string[] args) { int[] arr = new int[] {0 0 0 0 0}; int n = arr.Length; constructBITree(arrn); // Add 2 to all the // element from [24] int l = 2 r = 4 val = 2; update(l r n val); int index = 4; Console.WriteLine('Element at index ' + index + ' is ' + getSum(index)); // Add 2 to all the // element from [03] l = 0; r = 3; val = 4; update(l r n val); // Find the element // at Index 3 index = 3; Console.WriteLine('Element at index ' + index + ' is ' + getSum(index)); } } // This code is contributed by Shrikant13
// Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. function updateBIT(BITree n index val) { // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent in update View index += index & (-index); } } // Constructs and returns a Binary Indexed Tree for given // array of size n. function constructBITree(arr n) { // Create and initialize BITree[] as 0 let BITree = new Array(n+1).fill(0); // Store the actual values in BITree[] using update() for (let i = 0; i < n; i++) { updateBIT(BITree n i arr[i]); } return BITree; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] function getSum(BITree index) { let sum = 0; // Initialize result // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Updates such that getElement() gets an increased // value when queried from l to r. function update(BITree l r n val) { // Increase value at 'l' by 'val' updateBIT(BITree n l val); // Decrease value at 'r+1' by 'val' updateBIT(BITree n r+1 -val); } // Test the functions let arr = [0 0 0 0 0]; let n = arr.length; let BITree = constructBITree(arr n); // Add 2 to all the element from [24] let l = 2 r = 4 val = 2; update(BITree l r n val); // Find the element at Index 4 let index = 4; console.log(`Element at index ${index} is ${getSum(BITreeindex)}`); // Add 2 to all the element from [03] l = 0 r = 3 val = 4; update(BITree l r n val); // Find the element at Index 3 index = 3; console.log(`Element at index ${index} is ${getSum(BITreeindex)}`);
산출:
자바 문자열의 값
Element at index 4 is 2 Element at index 3 is 6
시간 복잡도: O(q * log n) + O(n * log n) 여기서 q는 쿼리 수입니다.
보조 공간: 에)
대부분의 쿼리가 getElement()인 경우 방법 1이 효율적입니다. 방법 2는 대부분의 쿼리가 업데이트()인 경우 효율적이고, 두 쿼리가 혼합된 경우 방법 3이 선호됩니다.