Dada una array arr[] de tamaño N y la tarea es responder consultas Q de los siguientes tipos:
- 1 X 0: agregue X en la parte posterior de la array.
- 2 XY: Establezca arr[X] = Y .
- 3 X 0: Eliminar arr[X] .
- 4 XY: Encuentra la suma en el rango [X, Y] .
Tenga en cuenta que después de eliminar arr[X] en el tipo de consulta 3 , todos los elementos después del índice X se desplazarán una posición a la izquierda.
Ejemplos:
Entrada: arr[] = {1, 2, 5, 3, 4}, Q[][] = {
{4, 2, 4},
{3, 3, 0},
{1, 6, 0},
{ 4, 3, 5}}
Salida:
10
13
Primera consulta -> sum(arr[1], arr[2], arr[3])
Segunda consulta -> arr[] = { 1, 2, 3, 4 }
Tercera Consulta -> arr[] = { 1, 2, 3, 4, 6 }
Cuarta consulta -> sum(arr[2], arr[3], arr[4])Entrada: arr[] = {1, 2, 3, 4, 5}, Q[][] = {
{4, 1, 5},
{3, 3, 0},
{1, 6, 0},
{ 4, 3, 5},
{2, 4, 10}.
{4, 1, 5}}
Salida:
15
15
23
Enfoque ingenuo: la forma ingenua de resolver este problema es ejecutar las consultas directamente en la array dada, que tendrá una complejidad de tiempo de O(Q * N) .
Enfoque eficiente:
- Como hay algunas estructuras de datos como el árbol de segmentos o BIT (Fenwick Tree) que proporcionan la actualización de puntos y la suma de rango en O (logN) por consulta.
- La publicación utiliza un Fenwick Tree para hacer lo mismo, por lo que se recomienda realizar la actualización de puntos en Fenwick Tree .
- Pero el principal problema es realizar la operación de eliminación ( consultas de tipo 3 ). Después de realizar, existe la necesidad de cambiar, lo que nuevamente conducirá a O (Q * N) en el peor de los casos.
- Se puede usar un truco que, después de eliminar un elemento, simplemente actualice el valor en A[X] = 0 y asigne el índice después de X a X + número de elementos eliminados antes de X .
- Para encontrar la cantidad de elementos eliminados antes de X , se usará otro árbol de Fenwick (como idx en la implementación) y seguirá agregando 1 en ese índice donde se realiza la operación de eliminación.
- Esto significa que al momento de obtener u obtener un índice en particular, se puede realizar una consulta al árbol idx y actualizar el índice X a X + sum(X, idx) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Size of the array (MAX)
const int N = 2e5 + 10;
// To store the sum of
// the array elements
vector<int> bit(N, 0);
// To keep track of how many type 3
// queries have been performed before
// a particular index
vector<int> idx(N, 0);
// Function to perform the point
// update in Fenwick tree
void update(int idx, int val,
vector<int>& bitt)
{
while (idx < N) {
bitt[idx] += val;
idx += idx & (-idx);
}
}
// Function to return the sum
// of the elements A[1...idx]
// from BIT
int sum(int idx,
vector<int>& bitt)
{
int res = 0;
while (idx > 0) {
res += bitt[idx];
idx -= idx & (-idx);
}
return res;
}
// Function to perform the queries and
// return the answer vector
vector<int> performQueries(vector<int>& A,
vector<vector<int> >& B)
{
// For 1 bases indexing
// insert 0 in the vector
A.insert(A.begin(), 0);
// Updated size of the vector
int n = (int)A.size();
// Updating the bit tree
for (int i = 1; i < n; ++i) {
update(i, A[i], bit);
}
// Vector to store the answers
// of range sum
vector<int> ans;
// Iterating in the query
// vector
for (auto i : B) {
int type = i[0];
int x = i[1], v = i[2];
// If the query is of
// type 1
if (type == 1) {
// Updating the tree
// with x in the last
update(n, x, bit);
// Pushing back the value
// in the original vector
A.push_back(x);
// Incrementing the size
// of the vector by 1
n++;
}
// If the query is of type 2
else if (type == 2) {
// Getting the updated index
// in case of any query of
// type 3 occurred before it
int id = x + sum(x, idx);
// Making the effect to that
// value to 0 by subtracting
// same value from the tree
update(id, -A[id], bit);
// Updating the A[id] to v
A[id] = v;
// Now update the
// bit by v at x
update(id, v, bit);
}
// If the query is of type 3
else if (type == 3) {
// Get the current index
int id = x + sum(x, idx);
// Remove the effect of that
// index from the bit tree
update(id, -A[id], bit);
// Update the idx tree
// because one element has
// been deleted
update(x, 1, idx);
// Update the idx val to 0
A[id] = 0;
}
// If the query is of type 4
else {
// Get the updated range
int xx = x + sum(x, idx);
int vv = v + sum(v, idx);
// Push_back the value
ans.push_back(sum(vv, bit)
- sum(xx - 1, bit));
}
}
return ans;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 5, 3, 4 };
// Queries
vector<vector<int> > B = {
{ 4, 2, 4 },
{ 3, 3, 0 },
{ 1, 6, 0 },
{ 4, 3, 5 },
};
// Get the answer array
vector<int> ans = performQueries(A, B);
// printing the answer
for (int i : ans)
cout << i << "\n";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Size of the array (MAX)
static int N = (int) 2e5 + 10;
// To store the sum of
// the array elements
static int[] bit = new int[N];
// To keep track of how many type 3
// queries have been performed before
// a particular index
static int[] idx = new int[N];
// Function to perform the point
// update in Fenwick tree
static void update(int idx, int val, int[] bitt) {
while (idx < N) {
bitt[idx] += val;
idx += idx & (-idx);
}
}
// Function to return the sum
// of the elements A[1...idx]
// from BIT
static int sum(int idx, int[] bitt) {
int res = 0;
while (idx > 0) {
res += bitt[idx];
idx -= idx & (-idx);
}
return res;
}
// Function to perform the queries and
// return the answer vector
static Vector<Integer> performQueries(Vector<Integer> A, int[][] B) {
// For 1 bases indexing
// insert 0 in the vector
A.insertElementAt(0, 0);
// Updated size of the vector
int n = (int) A.size();
// Updating the bit tree
for (int i = 1; i < n; ++i) {
update(i, A.elementAt(i), bit);
}
// Vector to store the answers
// of range sum
Vector<Integer> ans = new Vector<>();
// Iterating in the query
// vector
for (int[] i : B) {
int type = i[0];
int x = i[1], v = i[2];
// If the query is of
// type 1
if (type == 1) {
// Updating the tree
// with x in the last
update(n, x, bit);
// Pushing back the value
// in the original vector
A.add(x);
// Incrementing the size
// of the vector by 1
n++;
}
// If the query is of type 2
else if (type == 2) {
// Getting the updated index
// in case of any query of
// type 3 occurred before it
int id = x + sum(x, idx);
// Making the effect to that
// value to 0 by subtracting
// same value from the tree
update(id, -A.elementAt(id), bit);
// Updating the A[id] to v
A.set(id, v);
// Now update the
// bit by v at x
update(id, v, bit);
}
// If the query is of type 3
else if (type == 3) {
// Get the current index
int id = x + sum(x, idx);
// Remove the effect of that
// index from the bit tree
update(id, -A.elementAt(id), bit);
// Update the idx tree
// because one element has
// been deleted
update(x, 1, idx);
// Update the idx val to 0
A.set(id, 0);
}
// If the query is of type 4
else {
// Get the updated range
int xx = x + sum(x, idx);
int vv = v + sum(v, idx);
// Push_back the value
ans.add(sum(vv, bit) - sum(xx - 1, bit));
}
}
return ans;
}
// Driver Code
public static void main(String[] args) {
Integer[] a = { 1, 2, 5, 3, 4 };
Vector<Integer> A = new Vector<Integer>(Arrays.asList(a));
// Queries
int[][] B = { { 4, 2, 4 }, { 3, 3, 0 }, { 1, 6, 0 }, { 4, 3, 5 } };
// Get the answer array
Vector<Integer> ans = peformQueries(A, B);
// printing the answer
for (int i : ans)
System.out.println(i);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python implementation of the approach # Size of the array (MAX) N = int(2e5) + 10 # To store the sum of # the array elements bit = [0] * N # To keep track of how many type 3 # queries have been performed before # a particular index idx = [0] * N # Function to perform the point # update in Fenwick tree def update(index: int, val: int, bitt: list): while index < N: bitt[index] += val index += index & -index # Function to return the sum # of the elements A[1...idx] # from BIT def summation(index: int, bitt: list) -> int: res = 0 while index > 0: res += bitt[index] index -= index & -index return res # Function to perform the queries and # return the answer vector def performQueries(A: list, B: list) -> list: global bit, idx # For 1 bases indexing # insert 0 in the vector A.insert(0, 0) # Updated size of the vector n = len(A) # Updating the bit tree for i in range(1, n): update(i, A[i], bit) # Vector to store the answers # of range sum ans = [] # Iterating in the query # vector for i in B: type = i[0] x = i[1] v = i[2] # If the query is of # type 1 if type == 1: # Updating the tree # with x in the last update(n, x, bit) # Pushing back the value # in the original vector A.append(x) # Incrementing the size # of the vector by 1 n += 1 # If the query is of type 2 elif type == 2: # Getting the updated index # in case of any query of # type 3 occurred before it id = x + summation(x, idx) # Making the effect to that # value to 0 by subtracting # same value from the tree update(id, -A[id], bit) # Updating the A[id] to v A[id] = v # Now update the # bit by v at x update(id, v, bit) # If the query is of type 3 elif type == 3: # Get the current index id = x + summation(x, idx) # Remove the effect of that # index from the bit tree update(id, -A[id], bit) # Update the idx tree # because one element has # been deleted update(x, 1, idx) # Update the idx val to 0 A[id] = 0 # If the query is of type 4 else: # Get the updated range xx = x + summation(x, idx) vv = v + summation(v, idx) # Push_back the value ans.append(summation(vv, bit) - summation(xx - 1, bit)) return ans # Driver Code if __name__ == "__main__": A = [1, 2, 5, 3, 4] # Queries B = [[4, 2, 4], [3, 3, 0], [1, 6, 0], [4, 3, 5]] # Get the answer array ans = performQueries(A, B) # printing the answer for i in ans: print(i) # This code is contributed by # sanjeev2552
Javascript
<script>
// Javascript implementation of the approach
// Size of the array (MAX)
const N = 2e5 + 10;
// To store the sum of
// the array elements
let bit = new Array(N).fill(0);
// To keep track of how many type 3
// queries have been performed before
// a particular index
let idx = new Array(N).fill(0);
// Function to perform the point
// update in Fenwick tree
function update(idx, val, bitt) {
while (idx < N) {
bitt[idx] += val;
idx += idx & (-idx);
}
}
// Function to return the sum
// of the elements A[1...idx]
// from BIT
function sum(idx, bitt) {
let res = 0;
while (idx > 0) {
res += bitt[idx];
idx -= idx & (-idx);
}
return res;
}
// Function to perform the queries and
// return the answer vector
function performQueries(A, B) {
// For 1 bases indexing
// insert 0 in the vector
A.unshift(0);
// Updated size of the vector
let n = A.length;
// Updating the bit tree
for (let i = 1; i < n; ++i) {
update(i, A[i], bit);
}
// Vector to store the answers
// of range sum
let ans = new Array();
// Iterating in the query
// vector
for (let i of B) {
let type = i[0];
let x = i[1], v = i[2];
// If the query is of
// type 1
if (type == 1) {
// Updating the tree
// with x in the last
update(n, x, bit);
// Pushing back the value
// in the original vector
A.push(x);
// Incrementing the size
// of the vector by 1
n++;
}
// If the query is of type 2
else if (type == 2) {
// Getting the updated index
// in case of any query of
// type 3 occurred before it
let id = x + sum(x, idx);
// Making the effect to that
// value to 0 by subtracting
// same value from the tree
update(id, -A[id], bit);
// Updating the A[id] to v
A[id] = v;
// Now update the
// bit by v at x
update(id, v, bit);
}
// If the query is of type 3
else if (type == 3) {
// Get the current index
let id = x + sum(x, idx);
// Remove the effect of that
// index from the bit tree
update(id, -A[id], bit);
// Update the idx tree
// because one element has
// been deleted
update(x, 1, idx);
// Update the idx val to 0
A[id] = 0;
}
// If the query is of type 4
else {
// Get the updated range
let xx = x + sum(x, idx);
let vv = v + sum(v, idx);
// Push the value
ans.push(sum(vv, bit)
- sum(xx - 1, bit));
}
}
return ans;
}
// Driver code
let A = [1, 2, 5, 3, 4];
// Queries
let B = [
[4, 2, 4],
[3, 3, 0],
[1, 6, 0],
[4, 3, 5],
];
// Get the answer array
let ans = peformQueries(A, B);
// printing the answer
for (let i of ans)
document.write(i + "<br>");
// This code is contributed by gfgking
</script>
Producción:
10 13
Complejidad Temporal: O(Q * logN + NlogN)
Espacio Auxiliar : O(N).