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].
- getElement(i) : Encuentra el elemento en la array indexada en ‘i’.
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 consulta puntual.
Ejemplo:
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}
Método 1 [actualización: O(n), getElement() : O(1)]
- actualizar (l, r, val): iterar sobre el subarreglo de l a r y aumentar todos los elementos por val.
- getElement(i): Para obtener el elemento en el i-ésimo índice, simplemente devuelva arr[i].
La complejidad temporal en el peor de los casos es O(q*n) donde q es el número de consultas y n es el número de elementos.
Método 2 [actualización: O(1), getElement(): O(n)]
¡Podemos evitar actualizar todos los elementos y podemos actualizar solo 2 índices de la array!
- actualizar (l, r, val): agregue ‘val’ al elemento l -th y reste ‘ val ‘ del elemento (r + 1) , haga esto para todas las consultas de actualización.
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
- getElement(i) : Para obtener el i -ésimo elemento en la array, busque la suma de todos los enteros en la array de 0 a i. (Prefijo Suma).
Analicemos la consulta de actualización. ¿Por qué agregar val al l -ésimo índice? Agregar val al l -ésimo índice significa que todos los elementos después de l se incrementan en val, ya que calcularemos la suma del prefijo para cada elemento. ¿Por qué restar val de (r+1) el índice th ? Se requería una actualización de rango de [l,r], pero lo que hemos actualizado es [l, n-1], por lo que debemos eliminar el valor de todos los elementos después de r, es decir, restar el valor de (r+1) el índice . Por lo tanto, el val se suma al rango [l,r]. A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to demonstrate Range Update
// and Point Queries Without using BIT
#include <bits/stdc++.h>
using namespace std;
// Updates such that getElement() gets an increased
// value when queried from l to r.
void update(int arr[], int l, int r, int val)
{
arr[l] += val;
arr[r+1] -= val;
}
// Get the element indexed at i
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
int main()
{
int arr[] = {0, 0, 0, 0, 0};
int n = sizeof(arr) / sizeof(arr[0]);
int l = 2, r = 4, val = 2;
update(arr, l, r, val);
//Find the element at Index 4
int index = 4;
cout << "Element at index " << index << " is " <<
getElement(arr, index) << endl;
l = 0, r = 3, val = 4;
update(arr,l,r,val);
//Find the element at Index 3
index = 3;
cout << "Element at index " << index << " is " <<
getElement(arr, index) << endl;
return 0;
}
Java
// 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(arr,l,r,val);
//Find the element at Index 3
index = 3;
System.out.println("Element at index " + index + " is " +getElement(arr, index));
}
}
Python3
# 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#
// 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(arr,l,r,val);
//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
<?php
// 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
?>
Producción:
Element at index 4 is 2 Element at index 3 is 6
Complejidad temporal : O(q*n) donde q es el número de consultas.
Método 3 (usando el árbol indexado binario)
En el método 2, hemos visto que el problema puede reducirse a consultas de actualización y suma de prefijos. Hemos visto que BIT se puede usar para realizar consultas de actualización y suma de prefijos en tiempo O (Inicio de sesión). A continuación se muestra la implementación.
C++
// C++ code to demonstrate Range Update and
// Point Queries on a Binary Index Tree
#include <bits/stdc++.h>
using namespace std;
// 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);
}
}
// Constructs and returns a Binary Indexed Tree for given
// array of size n.
int *constructBITree(int arr[], int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
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(BITree, n, i, arr[i]);
// Uncomment below lines to see contents of BITree[]
//for (int i=1; i<=n; i++)
// cout << BITree[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[]
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 such that getElement() gets an increased
// value when queried from l to r.
void update(int BITree[], int l, int r, int n, int 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 program to test above function
int main()
{
int arr[] = {0, 0, 0, 0, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int *BITree = constructBITree(arr, n);
// Add 2 to all the element from [2,4]
int l = 2, r = 4, val = 2;
update(BITree, l, r, n, val);
// Find the element at Index 4
int index = 4;
cout << "Element at index " << index << " is " <<
getSum(BITree,index) << "\n";
// Add 2 to all the element from [0,3]
l = 0, r = 3, val = 4;
update(BITree, l, r, n, val);
// Find the element at Index 3
index = 3;
cout << "Element at index " << index << " is " <<
getSum(BITree,index) << "\n" ;
return 0;
}
Java
/* 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(arr,n);
// Add 2 to all the
// element from [2,4]
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 [0,3]
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
# 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 [2,4]
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 [0,3]
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(BITree,index))
# This code is contributed by mohit kumar 29
C#
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(arr,n);
// Add 2 to all the
// element from [2,4]
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 [0,3]
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
Producción:
Element at index 4 is 2 Element at index 3 is 6
Complejidad de tiempo: O(q * log n) + O(n * log n) donde q es el número de consultas. El método 1 es eficiente cuando la mayoría de las consultas son getElement(), el método 2 es eficiente cuando la mayoría de las consultas son actualizaciones() y se prefiere el método 3 cuando hay una combinación de ambas 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