Dada una array arr[0..n-1]. Es necesario realizar las siguientes operaciones.
- actualizar (l, r, val) : agrega ‘val’ a todos los elementos en la array desde [l, r].
- getRangeSum(l, r) : Encuentra la suma de todos los elementos en el arreglo de [l, r].
Inicialmente, todos los elementos de la array son 0. Las consultas pueden estar en cualquier orden, es decir, puede haber muchas actualizaciones antes de la suma del rango.
Ejemplo:
Input : n = 5 // {0, 0, 0, 0, 0}
Queries: update : l = 0, r = 4, val = 2
update : l = 3, r = 4, val = 3
getRangeSum : l = 2, r = 4
Output: Sum of elements of range [2, 4] is 12
Explanation : Array after first update becomes
{2, 2, 2, 2, 2}
Array after second update becomes
{2, 2, 2, 5, 5}
En la publicación anterior , discutimos la actualización de rango y las soluciones de consulta de puntos usando BIT.
rangeUpdate(l, r, val) : Agregamos ‘val’ al elemento en el índice ‘l’. Restamos ‘val’ del elemento en el índice ‘r+1’.
getElement(index) [o getSum()]: devolvemos la suma de los elementos de 0 al índice que se puede obtener rápidamente usando BIT.
Podemos calcular rangeSum() usando consultas getSum().
rangeSum(l, r) = getSum(r) – getSum(l-1)
Una solución simple es usar las soluciones discutidas en la publicación anterior . La consulta de actualización de rango es la misma. La consulta de suma de rango se puede lograr al obtener una consulta para todos los elementos en el rango.
Una solución eficientees asegurarse de que ambas consultas se puedan realizar en tiempo O (Inicio de sesión). Obtenemos la suma de rango usando sumas de prefijos. ¿Cómo asegurarse de que la actualización se realice de manera que la suma de prefijos se pueda realizar rápidamente? Considere una situación en la que se necesita la suma del prefijo [0, k] (donde 0 <= k < n) después de la actualización del rango en el rango [l, r]. Se plantean tres casos ya que k puede posiblemente estar en 3 regiones.
Caso 1 : 0 < k < l
La consulta de actualización no afectará a la consulta de suma.
Caso 2 : l <= k <= r
Considere un ejemplo:
Add 2 to range [2, 4], the resultant array would be: 0 0 2 2 2 If k = 3 Sum from [0, k] = 4
¿Cómo obtener este resultado?
Simplemente agregue el valor del l -ésimo índice al k -ésimo índice. La suma se incrementa en “val*(k) – val*(l-1)” después de la consulta de actualización.
Caso 3 : k > r
Para este caso, necesitamos agregar «val» del l -ésimo índice al r -ésimo índice. La suma se incrementa en “val*r – val*(l-1)” debido a la consulta de actualización.
Observaciones:
Caso 1: es simple ya que la suma permanecería igual que antes de la actualización.
Caso 2: La suma se incrementó en val*k – val*(l-1). Podemos encontrar “val”, es similar a encontrar el i -ésimo elemento en el artículo de actualización de rango y consulta de puntos. Por lo tanto, mantenemos un BIT para actualización de rango y consultas de puntos, este BIT será útil para encontrar el valor en el k -ésimo índice. Ahora que se calcula val * k, ¿cómo manejar el término extra val*(l-1)?
Para manejar este término adicional, mantenemos otro BIT (BIT2). Actualice val * (l-1) en el índice l , de modo que cuando se realice la consulta getSum en BIT2, el resultado será val * (l-1).
Caso 3: La suma en el caso 3 se incrementó en “val*r – val *(l-1)”, el valor de este término se puede obtener usando BIT2. En lugar de sumar, restamos “val*(l-1) – val*r” ya que podemos obtener este valor de BIT2 sumando val*(l-1) como hicimos en el caso 2 y restando val*r en cada actualización operación.
Update Query Update(BITree1, l, val) Update(BITree1, r+1, -val) UpdateBIT2(BITree2, l, val*(l-1)) UpdateBIT2(BITree2, r+1, -val*r) Range Sum getSum(BITTree1, k) *k) - getSum(BITTree2, k)
Implementación de la idea anterior
C++
// C++ program to demonstrate Range Update
// and Range Queries using BIT
#include <bits/stdc++.h>
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 [0,r] then subtract sum
// from [0,l-1] in order to find sum from
// [l,r]
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 Program to test above function
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 [0,4]
int l = 0 , r = 4 , val = 5;
updateRange(BITTree1,BITTree2,n,val,l,r);
// Add 2 to all the elements from [2,4]
l = 2 , r = 4 , val = 10;
updateRange(BITTree1,BITTree2,n,val,l,r);
// Find sum of all the elements from
// [1,4]
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 [0,r] then subtract sum
// from [0,l-1] in order to find sum from
// [l,r]
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 [0,4]
int l = 0 , r = 4 , val = 5;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Add 2 to all the elements from [2,4]
l = 2 ; r = 4 ; val = 10;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Find sum of all the elements from
// [1,4]
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
# Python 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 [0,r] then subtract sum
# from [0,l-1] in order to find sum from
# [l,r]
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 [0,4]
l = 0
r = 4
val = 5
updateRange(BITTree1, BITTree2, n, val, l, r)
# Add 2 to all the elements from [2,4]
l = 2
r = 4
val = 10
updateRange(BITTree1, BITTree2, n, val, l, r)
# Find sum of all the elements from
# [1,4]
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 [0,r] then subtract sum
// from [0,l-1] in order to find sum from
// [l,r]
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 [0,4]
int l = 0 , r = 4 , val = 5;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Add 2 to all the elements from [2,4]
l = 2 ; r = 4 ; val = 10;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Find sum of all the elements from
// [1,4]
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 [0,r] then subtract sum
// from [0,l-1] in order to find sum from
// [l,r]
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 [0,4]
let l = 0 , r = 4 , val = 5;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Add 2 to all the elements from [2,4]
l = 2 ; r = 4 ; val = 10;
updateRange(BITTree1, BITTree2, n, val, l, r);
// Find sum of all the elements from
// [1,4]
l = 1 ; r = 4;
document.write("Sum of elements from [" + l
+ "," + r+ "] is ");
document.write(rangeSum(l, r, BITTree1, BITTree2)+ "<br>");
// This code is contributed by rag2127
</script>
Producción:
Sum of elements from [1,4] is 50
Complejidad de tiempo : O(q*log(n)) donde q es el número de consultas.
Este artículo es una contribución de Chirag Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA