이진 인덱스 트리: 범위 업데이트 및 범위 쿼리
배열 arr[0..N-1]이 주어졌습니다. 다음 작업을 수행해야 합니다.
- 업데이트(l r val) : [l r]의 배열에 있는 모든 요소에 'val'을 추가합니다.
- getRangeSum(l r) : [l r]에서 배열의 모든 요소의 합을 찾습니다.
처음에 배열의 모든 요소는 0입니다. 쿼리는 순서에 관계없이 가능합니다. 즉, 범위 합계 이전에 많은 업데이트가 있을 수 있습니다.
예:
입력: N = 5 // {0 0 0 0 0}
쿼리: 업데이트: l = 0 r = 4 val = 2
업데이트 : l = 3 r = 4 val = 3
getRangeSum : l = 2 r = 4산출: 범위 [2 4]의 요소 합은 12입니다.
설명: 첫 번째 업데이트 후 배열은 {2 2 2 2 2}가 됩니다.
두 번째 업데이트 후 배열은 {2 2 2 5 5}가 됩니다.
순진한 접근 방식: 문제를 해결하려면 아래 아이디어를 따르십시오.
에서 이전 게시물 BIT를 사용한 범위 업데이트 및 포인트 쿼리 솔루션에 대해 논의했습니다.
rangeUpdate(l r val) : 인덱스 'l'의 요소에 'val'을 추가합니다. 인덱스 'r+1'에 있는 요소에서 'val'을 뺍니다.
getElement(index) [or getSum()]: BIT를 사용하여 빠르게 얻을 수 있는 0부터 인덱스까지의 요소 합계를 반환합니다.
getSum() 쿼리를 사용하여 rangeSum()을 계산할 수 있습니다.
rangeSum(l r) = getSum(r) - getSum(l-1)간단한 솔루션 에서 논의된 솔루션을 사용하는 것입니다. 이전 게시물 . 범위 업데이트 쿼리도 동일합니다. 범위 합계 쿼리는 범위의 모든 요소에 대해 가져오기 쿼리를 수행하여 수행할 수 있습니다.
효율적인 접근 방식: 문제를 해결하려면 아래 아이디어를 따르십시오.
접두사 합계를 사용하여 범위 합계를 얻습니다. 접두사 합계를 신속하게 수행할 수 있도록 업데이트가 수행되었는지 확인하는 방법은 무엇입니까? 접두사 합이 [0 k]인 상황을 고려하십시오(여기서 0 <= k < n) is needed after range update on the range [l r]. Three cases arise as k can possibly lie in 3 regions.
- 사례 1 : 0 < k < l
- 업데이트 쿼리는 합계 쿼리에 영향을 주지 않습니다.
- 사례 2 : 내가 <= k <= r
- 예를 들어 보겠습니다. 범위 [2 4]에 2를 추가하면 결과 배열은 다음과 같습니다. 0 0 2 2 2
k = 3인 경우 [0 k]의 합 = 4이 결과를 얻는 방법은 무엇입니까?
l의 val을 추가하기만 하면 됩니다. 일 k에 대한 인덱스 일 색인. 업데이트 쿼리 후 합계는 'val*(k) - val*(l-1)'만큼 증가합니다.
- 사례 3 : k > r
- 이 경우 l에서 'val'을 추가해야 합니다. 일 r에 대한 인덱스 일 색인. 업데이트 쿼리로 인해 합계가 'val*r – val*(l-1)'만큼 증가합니다.
관찰:
사례 1: 합계는 업데이트 전과 동일하게 유지되므로 간단합니다.
사례 2: 합계는 val*k - val*(l-1)만큼 증가했습니다. 우리는 'val'을 찾을 수 있습니다. 이는 i를 찾는 것과 비슷합니다. 일 요소 범위 업데이트 및 포인트 쿼리 기사 . 따라서 범위 업데이트 및 포인트 쿼리에 대해 하나의 BIT를 유지합니다. 이 BIT는 k에서 값을 찾는 데 도움이 됩니다. 일 색인. 이제 val * k는 추가 항 val*(l-1)을 처리하는 방법으로 계산됩니다.
이 추가 기간을 처리하기 위해 우리는 또 다른 BIT(BIT2)를 유지 관리합니다. l에서 val * (l-1) 업데이트 일 따라서 BIT2에서 getSum 쿼리가 수행되면 결과가 val*(l-1)로 제공됩니다.
사례 3: 사례 3의 합은 'val*r - val *(l-1)'만큼 증가되었으며 이 항의 값은 BIT2를 사용하여 얻을 수 있습니다. 추가하는 대신 'val*(l-1) - val*r'을 뺍니다. 사례 2에서 했던 것처럼 val*(l-1)을 추가하고 모든 업데이트 작업에서 val*r을 빼서 BIT2에서 이 값을 얻을 수 있기 때문입니다.
쿼리 업데이트
업데이트(BITree1 l val)
업데이트(BITree1 r+1 -val)
UpdateBIT2(BITree2 l val*(l-1))
업데이트BIT2(BITree2 r+1 -val*r)범위 합계
getSum(BITTree1 k) *k) - getSum(BITTree2 k)
문제를 해결하려면 아래 단계를 따르십시오.
- 주어진 함수 constructorBITree()를 사용하여 두 개의 이진 인덱스 트리를 만듭니다.
- 주어진 범위에서 합계를 찾으려면 주어진 범위와 이진 인덱스 트리를 매개변수로 사용하여 rangeSum() 함수를 호출하세요.
- [0 X] 범위의 합계를 반환하는 함수 sum을 호출합니다.
- 합계(R) - 합계(L-1) 반환
- 이 함수 내에서 [0 X]에서 배열의 합계를 반환하는 getSum() 함수를 호출합니다.
- 반환 getSum(Tree1 x) * x - getSum(tree2 x)
- getSum() 함수 내에서 0과 동일한 정수 합계를 생성하고 인덱스를 1만큼 증가시킵니다.
- 인덱스가 0보다 크면 합계를 Tree[index]로 늘립니다.
- 인덱스를 트리의 상위 노드로 이동하려면 (index & (-index))만큼 인덱스를 줄입니다.
- 반환 금액
- 주어진 범위의 합계를 인쇄합니다.
다음은 위의 접근 방식을 구현한 것입니다.
C++ // C++ program to demonstrate Range Update // and Range Queries using BIT #include using namespace std ; // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] int getSum ( int BITree [] 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 sum ; } // 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. void updateBIT ( int BITree [] 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 BI Tree BITree [ index ] += val ; // Update index to that of parent in update View index += index & ( - index ); } } // Returns the sum of array from [0 x] int sum ( int x int BITTree1 [] int BITTree2 []) { return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ); } void updateRange ( int BITTree1 [] int BITTree2 [] int n int val int l int r ) { // Update Both the Binary Index Trees // As discussed in the article // Update BIT1 updateBIT ( BITTree1 n l val ); updateBIT ( BITTree1 n r + 1 - val ); // Update BIT2 updateBIT ( BITTree2 n l val * ( l - 1 )); updateBIT ( BITTree2 n r + 1 - val * r ); } int rangeSum ( int l int r int BITTree1 [] int BITTree2 []) { // Find sum from [0r] then subtract sum // from [0l-1] in order to find sum from // [lr] return sum ( r BITTree1 BITTree2 ) - sum ( l - 1 BITTree1 BITTree2 ); } int * constructBITree ( int n ) { // Create and initialize BITree[] as 0 int * BITree = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; return BITree ; } // Driver code int main () { int n = 5 ; // Construct two BIT int * BITTree1 * BITTree2 ; // BIT1 to get element at any index // in the array BITTree1 = constructBITree ( n ); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree ( n ); // Add 5 to all the elements from [04] int l = 0 r = 4 val = 5 ; updateRange ( BITTree1 BITTree2 n val l r ); // Add 10 to all the elements from [24] l = 2 r = 4 val = 10 ; updateRange ( BITTree1 BITTree2 n val l r ); // Find sum of all the elements from // [14] l = 1 r = 4 ; cout < < 'Sum of elements from [' < < l < < '' < < r < < '] is ' ; cout < < rangeSum ( l r BITTree1 BITTree2 ) < < ' n ' ; return 0 ; }
Java // Java program to demonstrate Range Update // and Range Queries using BIT import java.util.* ; class GFG { // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] static int getSum ( int BITree [] 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 sum ; } // 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. static void updateBIT ( int BITree [] 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 BI Tree BITree [ index ] += val ; // Update index to that of parent in update View index += index & ( - index ); } } // Returns the sum of array from [0 x] static int sum ( int x int BITTree1 [] int BITTree2 [] ) { return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ); } static void updateRange ( int BITTree1 [] int BITTree2 [] int n int val int l int r ) { // Update Both the Binary Index Trees // As discussed in the article // Update BIT1 updateBIT ( BITTree1 n l val ); updateBIT ( BITTree1 n r + 1 - val ); // Update BIT2 updateBIT ( BITTree2 n l val * ( l - 1 )); updateBIT ( BITTree2 n r + 1 - val * r ); } static int rangeSum ( int l int r int BITTree1 [] int BITTree2 [] ) { // Find sum from [0r] then subtract sum // from [0l-1] in order to find sum from // [lr] return sum ( r BITTree1 BITTree2 ) - sum ( l - 1 BITTree1 BITTree2 ); } static int [] constructBITree ( int n ) { // Create and initialize BITree[] as 0 int [] BITree = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; return BITree ; } // Driver Program to test above function public static void main ( String [] args ) { int n = 5 ; // Contwo BIT int [] BITTree1 ; int [] BITTree2 ; // BIT1 to get element at any index // in the array BITTree1 = constructBITree ( n ); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree ( n ); // Add 5 to all the elements from [04] int l = 0 r = 4 val = 5 ; updateRange ( BITTree1 BITTree2 n val l r ); // Add 10 to all the elements from [24] l = 2 ; r = 4 ; val = 10 ; updateRange ( BITTree1 BITTree2 n val l r ); // Find sum of all the elements from // [14] l = 1 ; r = 4 ; System . out . print ( 'Sum of elements from [' + l + '' + r + '] is ' ); System . out . print ( rangeSum ( l r BITTree1 BITTree2 ) + 'n' ); } } // This code is contributed by 29AjayKumar
Python3 # Python3 program to demonstrate Range Update # and Range Queries using BIT # 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 : list index : int ) -> int : summ = 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 summ += BITree [ index ] # Move index to parent node in getSum View index -= index & ( - index ) return summ # 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 ( BITTree : list n : int index : int val : int ) -> None : # 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 BITTree [ index ] += val # Update index to that of parent in update View index += index & ( - index ) # Returns the sum of array from [0 x] def summation ( x : int BITTree1 : list BITTree2 : list ) -> int : return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ) def updateRange ( BITTree1 : list BITTree2 : list n : int val : int l : int r : int ) -> None : # Update Both the Binary Index Trees # As discussed in the article # Update BIT1 updateBit ( BITTree1 n l val ) updateBit ( BITTree1 n r + 1 - val ) # Update BIT2 updateBit ( BITTree2 n l val * ( l - 1 )) updateBit ( BITTree2 n r + 1 - val * r ) def rangeSum ( l : int r : int BITTree1 : list BITTree2 : list ) -> int : # Find sum from [0r] then subtract sum # from [0l-1] in order to find sum from # [lr] return summation ( r BITTree1 BITTree2 ) - summation ( l - 1 BITTree1 BITTree2 ) # Driver Code if __name__ == '__main__' : n = 5 # BIT1 to get element at any index # in the array BITTree1 = [ 0 ] * ( n + 1 ) # BIT 2 maintains the extra term # which needs to be subtracted BITTree2 = [ 0 ] * ( n + 1 ) # Add 5 to all the elements from [04] l = 0 r = 4 val = 5 updateRange ( BITTree1 BITTree2 n val l r ) # Add 10 to all the elements from [24] l = 2 r = 4 val = 10 updateRange ( BITTree1 BITTree2 n val l r ) # Find sum of all the elements from # [14] l = 1 r = 4 print ( 'Sum of elements from [ %d %d ] is %d ' % ( l r rangeSum ( l r BITTree1 BITTree2 ))) # This code is contributed by # sanjeev2552
C# // C# program to demonstrate Range Update // and Range Queries using BIT using System ; class GFG { // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] static int getSum ( int [] BITree 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 sum ; } // 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. static void updateBIT ( int [] BITree 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 BI Tree BITree [ index ] += val ; // Update index to that of // parent in update View index += index & ( - index ); } } // Returns the sum of array from [0 x] static int sum ( int x int [] BITTree1 int [] BITTree2 ) { return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ); } static void updateRange ( int [] BITTree1 int [] BITTree2 int n int val int l int r ) { // Update Both the Binary Index Trees // As discussed in the article // Update BIT1 updateBIT ( BITTree1 n l val ); updateBIT ( BITTree1 n r + 1 - val ); // Update BIT2 updateBIT ( BITTree2 n l val * ( l - 1 )); updateBIT ( BITTree2 n r + 1 - val * r ); } static int rangeSum ( int l int r int [] BITTree1 int [] BITTree2 ) { // Find sum from [0r] then subtract sum // from [0l-1] in order to find sum from // [lr] return sum ( r BITTree1 BITTree2 ) - sum ( l - 1 BITTree1 BITTree2 ); } static int [] constructBITree ( int n ) { // Create and initialize BITree[] as 0 int [] BITree = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; return BITree ; } // Driver Code public static void Main ( String [] args ) { int n = 5 ; // Contwo BIT int [] BITTree1 ; int [] BITTree2 ; // BIT1 to get element at any index // in the array BITTree1 = constructBITree ( n ); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree ( n ); // Add 5 to all the elements from [04] int l = 0 r = 4 val = 5 ; updateRange ( BITTree1 BITTree2 n val l r ); // Add 10 to all the elements from [24] l = 2 ; r = 4 ; val = 10 ; updateRange ( BITTree1 BITTree2 n val l r ); // Find sum of all the elements from // [14] l = 1 ; r = 4 ; Console . Write ( 'Sum of elements from [' + l + '' + r + '] is ' ); Console . Write ( rangeSum ( l r BITTree1 BITTree2 ) + 'n' ); } } // This code is contributed by 29AjayKumar
JavaScript < script > // JavaScript program to demonstrate Range Update // and Range Queries using BIT // 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 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 ); } } // Returns the sum of array from [0 x] function sum ( x BITTree1 BITTree2 ) { return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ); } function updateRange ( BITTree1 BITTree2 n val l r ) { // Update Both the Binary Index Trees // As discussed in the article // Update BIT1 updateBIT ( BITTree1 n l val ); updateBIT ( BITTree1 n r + 1 - val ); // Update BIT2 updateBIT ( BITTree2 n l val * ( l - 1 )); updateBIT ( BITTree2 n r + 1 - val * r ); } function rangeSum ( l r BITTree1 BITTree2 ) { // Find sum from [0r] then subtract sum // from [0l-1] in order to find sum from // [lr] return sum ( r BITTree1 BITTree2 ) - sum ( l - 1 BITTree1 BITTree2 ); } function constructBITree ( n ) { // Create and initialize BITree[] as 0 let BITree = new Array ( n + 1 ); for ( let i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; return BITree ; } // Driver Program to test above function let n = 5 ; // Contwo BIT let BITTree1 ; let BITTree2 ; // BIT1 to get element at any index // in the array BITTree1 = constructBITree ( n ); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree ( n ); // Add 5 to all the elements from [04] let l = 0 r = 4 val = 5 ; updateRange ( BITTree1 BITTree2 n val l r ); // Add 10 to all the elements from [24] l = 2 ; r = 4 ; val = 10 ; updateRange ( BITTree1 BITTree2 n val l r ); // Find sum of all the elements from // [14] l = 1 ; r = 4 ; document . write ( 'Sum of elements from [' + l + '' + r + '] is ' ); document . write ( rangeSum ( l r BITTree1 BITTree2 ) + '
' ); // This code is contributed by rag2127 < /script>
산출
Sum of elements from [14] is 50
시간 복잡도 : O(q * log(N)) 여기서 q는 쿼리 수입니다.
보조 공간: 에)
