DVEJETAINIS INDEKSUOTAS MEDIS: DIAPAZONO ATNAUJINIMAS IR DIAPAZONO UŽKLAUSOS

Duotas masyvas arr[0..N-1]. Reikia atlikti šias operacijas.

atnaujinimas (l r val) : pridėkite „val“ prie visų masyvo elementų iš [l r].
gautiRangeSum(l r) : Raskite visų masyvo elementų sumą iš [l r].

Iš pradžių visi masyvo elementai yra 0. Užklausos gali būti bet kokia tvarka, ty gali būti daug atnaujinimų prieš diapazono sumą.

Pavyzdys:

Įvestis: N = 5 // {0 0 0 0 0}
Užklausos: atnaujinimas: l = 0 r = 4 val = 2
atnaujinimas: l = 3 r = 4 val = 3
gautiRangeSum : l = 2 r = 4

Išvestis: Diapazono [2 4] elementų suma yra 12
Paaiškinimas: Masyvas po pirmojo atnaujinimo tampa {2 2 2 2 2}
Masyvas po antrojo atnaujinimo tampa {2 2 2 5 5}

Naivus požiūris: Norėdami išspręsti problemą, vadovaukitės toliau pateikta idėja:

Į ankstesnis įrašas aptarėme diapazono atnaujinimo ir taško užklausų sprendimus naudojant BIT.
rangeUpdate(l r val) : Prie indekso 'l' elemento pridedame 'val'. Mes atimame „val“ iš elemento, esančio indekse „r+1“.
getElement(index) [arba getSum()]: grąžiname elementų sumą nuo 0 iki indekso, kurią galima greitai gauti naudojant BIT.
Mes galime apskaičiuoti rangeSum() naudodami getSum() užklausas.
rangeSum(l r) = getSum(r) - getSum(l-1)
git add --all

Paprastas sprendimas yra naudoti sprendimus, aptartus ankstesnis įrašas . Diapazono atnaujinimo užklausa yra tokia pati. Diapazono sumos užklausą galima pasiekti atlikus visų diapazono elementų gavimo užklausą.

Efektyvus požiūris: Norėdami išspręsti problemą, vadovaukitės toliau pateikta idėja:

Mes gauname diapazono sumą naudodami priešdėlių sumas. Kaip įsitikinti, kad naujinimas atliktas taip, kad prefikso sumą būtų galima atlikti greitai? Apsvarstykite situaciją, kai priešdėlio suma [0 k] (kur 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 atvejis : 0< k < l
Atnaujinimo užklausa neturės įtakos sumos užklausai.
2 atvejis : l<= k <= r
Apsvarstykite pavyzdį: Pridėkite 2 prie diapazono [2 4], gautas masyvas būtų toks: 0 0 2 2 2
Jei k = 3, suma iš [0 k] = 4
Kaip gauti šį rezultatą?
Tiesiog pridėkite val nuo l^thindeksas į k^thindeksas. Po atnaujinimo užklausos suma padidinama „val*(k) – val*(l-1)“.

3 atvejis : k > r
Šiuo atveju turime pridėti „val“ iš l^thindeksas į r^thindeksas. Suma padidinama 'val*r – val*(l-1)' dėl atnaujinimo užklausos.

Pastebėjimai:

1 atvejis: yra paprasta, nes suma išliks tokia pati, kokia buvo prieš atnaujinimą.

2 atvejis: Suma padidinta val*k – val*(l-1). Galime rasti „val“, tai panašu į i radimą^thelementas viduje diapazono atnaujinimo ir taško užklausos straipsnis . Taigi mes palaikome vieną BIT diapazono atnaujinimui ir taškų užklausoms, šis BIT bus naudingas ieškant k reikšmę^thindeksas. Dabar apskaičiuojamas val * k, kaip tvarkyti papildomą terminą val*(l-1)?
Siekdami apdoroti šį papildomą terminą, palaikome kitą BIT (BIT2). Atnaujinti val * (l-1) adresu l^thindeksas, todėl kai užklausa getSum bus atlikta BIT2, rezultatas bus val*(l-1).

3 atvejis: 3 atveju suma buvo padidinta 'val*r - val *(l-1)', šio termino reikšmę galima gauti naudojant BIT2. Užuot pridėję, atimame „val*(l-1) - val*r“, nes šią reikšmę galime gauti iš BIT2 pridėdami val*(l-1), kaip padarėme 2 atveju, ir atimdami val*r kiekvienoje atnaujinimo operacijoje.

gimp kaip panaikinti pasirinkimą

Atnaujinti užklausą

Atnaujinimas (BITree1 l val)
Atnaujinimas (BITree1 r+1 -val)
AtnaujintiBIT2(BITree2 l val*(l-1))
AtnaujintiBIT2 (BITree2 r+1 -val*r)

Diapazono suma

getSum(BITTree1 k) *k) - getSum(BITTree2 k)

Norėdami išspręsti problemą, atlikite toliau nurodytus veiksmus.

Sukurkite du dvejetainius indekso medžius naudodami nurodytą funkciją constructBITree()
Norėdami rasti sumą tam tikrame diapazone, iškvieskite funkciją rangeSum() su parametrais kaip nurodyta diapazone ir dvejetainiais indeksuotais medžiais
- Iškvieskite funkcijos sumą, kuri grąžins sumą diapazone [0 X]
- Grąžinimo suma(R) – suma(L-1)
  - Šios funkcijos viduje iškvieskite funkciją getSum(), kuri grąžins masyvo sumą iš [0 X]
  - Grąžinti getSum(tree1 x) * x - getSum(tree2 x)
  - Funkcijos getSum() viduje sukurkite sveikojo skaičiaus sumą, lygią nuliui, ir padidinkite indeksą 1
  - Jei indeksas yra didesnis nei nulis, padidinkite sumą Tree[index]
  - Sumažinkite indeksą (index & (-index)), kad perkeltumėte indeksą į pagrindinį medžio mazgą
  - Grąžinimo suma
Atspausdinkite sumą duotame diapazone

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

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# 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(BITreeindex) {  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(BITreenindexval) {  // 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(xBITTree1BITTree2) {  return (getSum(BITTree1 x) * x) - getSum(BITTree2 x); } function updateRange(BITTree1BITTree2nvallr) {  // 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(lrBITTree1BITTree2) {  // 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>

Išvestis

Sum of elements from [14] is 50

Laiko sudėtingumas : O(q * log(N)), kur q yra užklausų skaičius.
Pagalbinė erdvė: O(N)

TechCodeview

Dvejetainis indeksuotas medis: diapazono atnaujinimas ir diapazono užklausos

Pastebėjimai: