الشجرة الثنائية المفهرسة: تحديث النطاق واستعلامات النطاق
نظرا لصفيف arr[0..N-1]. يجب تنفيذ العمليات التالية.
- تحديث (ل ص فال) : أضف "val" إلى جميع العناصر الموجودة في المصفوفة من [l r].
- getRangeSum(ل ص) : ابحث عن مجموع جميع العناصر في المصفوفة من [l r].
في البداية، تكون جميع العناصر الموجودة في المصفوفة 0. يمكن أن تكون الاستعلامات بأي ترتيب، أي يمكن أن يكون هناك العديد من التحديثات قبل مجموع النطاق.
مثال:
مدخل: ن = 5 // {0 0 0 0 0}
الاستعلامات: التحديث: ل = 0 ص = 4 فال = 2
التحديث : ل = 3 ص = 4 فال = 3
getRangeSum : ل = 2 ص = 4الإخراج: مجموع عناصر النطاق [2 4] هو 12
توضيح: يصبح المصفوفة بعد التحديث الأول {2 2 2 2 2}
يصبح المصفوفة بعد التحديث الثاني {2 2 2 5 5}
النهج الساذج: لحل المشكلة اتبع الفكرة التالية:
في المنشور السابق ناقشنا تحديث النطاق وحلول الاستعلام النقطي باستخدام BIT.
rangeUpdate(l r val): نضيف "val" إلى العنصر الموجود في الفهرس "l". نطرح "val" من العنصر الموجود في الفهرس "r+1".
getElement(index) [أو getSum()]: نعيد مجموع العناصر من 0 إلى الفهرس الذي يمكن الحصول عليه بسرعة باستخدام BIT.
يمكننا حساب rangeSum() باستخدام استعلامات getSum().
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 إلى النطاق [2 4] وستكون المصفوفة الناتجة: 0 0 2 2 2
إذا كان k = 3 المجموع من [0 k] = 4كيف تحصل على هذه النتيجة؟
ما عليك سوى إضافة val من l ذ مؤشر إلى ك ذ فِهرِس. يتم زيادة المجموع بمقدار 'val*(k) - val*(l-1)' بعد استعلام التحديث.
- الحالة 3 : ك > ص
- في هذه الحالة نحتاج إلى إضافة "val" من l ذ مؤشر إلى ص ذ فِهرِس. يتم زيادة المجموع بمقدار 'val*r – val*(l-1)' بسبب استعلام التحديث.
الملاحظات:
الحالة 1: الأمر بسيط حيث سيظل المبلغ كما كان قبل التحديث.
الحالة 2: تمت زيادة المبلغ بمقدار val*k - val*(l-1). يمكننا العثور على "val" وهو مشابه للعثور على i ذ عنصر في تحديث النطاق ومقالة استعلام النقطة . لذلك نحتفظ بت واحدة لتحديث النطاق واستعلامات النقاط، وستكون هذه البتة مفيدة في العثور على القيمة عند k ذ فِهرِس. الآن يتم حساب val * k كيفية التعامل مع المصطلح الإضافي val * (l-1)؟
ومن أجل التعامل مع هذا المصطلح الإضافي، نحتفظ بمعاهدة ثنائية أخرى (BIT2). تحديث val * (l-1) عند l ذ فهرس لذلك عند تنفيذ استعلام getSum على BIT2 سيعطي النتيجة كـ val*(l-1).
الحالة 3: تمت زيادة المبلغ في الحالة 3 بواسطة 'val*r - val *(l-1)' ويمكن الحصول على قيمة هذا المصطلح باستخدام BIT2. بدلاً من الإضافة، نطرح 'val*(l-1) - val*r' حيث يمكننا الحصول على هذه القيمة من BIT2 عن طريق إضافة val*(l-1) كما فعلنا في الحالة 2 وطرح val*r في كل عملية تحديث.
تحديث الاستعلام
تحديث (BITree1 لتر فال)
تحديث(BITree1 r+1 -val)
UpdateBIT2(BITree2 l val*(l-1))
UpdateBIT2(BITree2 r+1 -val*r)مجموع النطاق
getSum(BITTree1 ك) *ك) - getSum(BITTree2 ك)
اتبع الخطوات التالية لحل المشكلة:
- قم بإنشاء شجرتي الفهرس الثنائي باستخدام الوظيفة المحددة buildBITree()
- للعثور على المجموع في نطاق معين، قم باستدعاء الدالة rangeSum() مع المعلمات مثل النطاق المحدد والأشجار المفهرسة الثنائية
- استدعاء مجموع الدالة الذي سيرجع مجموعًا في النطاق [0 X]
- مجموع الإرجاع(R) - المجموع(L-1)
- داخل هذه الوظيفة، قم باستدعاء الدالة getSum() والتي ستعيد مجموع المصفوفة من [0 X]
- إرجاع getSum(Tree1 x) * x - getSum(tree2 x)
- داخل الدالة getSum()، أنشئ مجموعًا صحيحًا يساوي الصفر وقم بزيادة الفهرس بمقدار 1
- عندما يكون الفهرس أكبر من الصفر، قم بزيادة المجموع بواسطة 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 هو عدد الاستعلامات.
المساحة المساعدة: على)
