Dada una array A[ ] que consta de enteros no negativos y una array Q[ ][ ] que consta de consultas de los siguientes dos tipos:
- (1, l, val): actualice A[l] a A[l] + val .
- (2, K): encuentre el límite inferior de K en la array de suma de prefijos de A[ ] . Si el límite_inferior no existe, imprima -1.
La tarea para cada consulta del segundo tipo es imprimir el índice del límite inferior del valor K.
Ejemplos:
Entrada: A[ ] = {1, 2, 3, 5, 8}, Q[ ][ ] = {{1, 0, 2}, {2, 5}, {1, 3, 5}}
Salida: 1
Explicación:
Consulta 1: actualice A[0] a A[0] + 2. Ahora A[ ] = {3, 2, 3, 5, 8}
Consulta 2: límite inferior de K = 5 en la array de suma de prefijos {3, 5, 8, 13, 21} es 5 e índice = 1.
Consulta 3: actualice A[3] a A[3] + 5. Ahora A[ ] = {3, 2, 3, 10, 8}Entrada: A[ ] = {4, 1, 12, 8, 20}, Q[ ] = {{2, 50}, {1, 3, 12}, {2, 50}}
Salida: -1
Enfoque ingenuo:
el enfoque más simple es construir primero una array de suma de prefijos de una array dada A[ ], y para consultas de Tipo 1 , actualizar valores y volver a calcular la suma de prefijos. Para consultas de tipo 2 , realice una búsqueda binaria en la array de suma de prefijos para encontrar el límite inferior .
Complejidad de tiempo: O(Q*(N*logn))
Espacio auxiliar: O(N)
Enfoque eficiente:
El enfoque anterior se puede optimizar Fenwick Tree . Con esta estructura de datos , las consultas de actualización en la array de suma de prefijos se pueden realizar en tiempo logarítmico.
Siga los pasos a continuación para resolver el problema:
- Construya la array de suma de prefijos utilizando Fenwick Tree.
- Para consultas de Tipo 1 , mientras que l > 0 , agregue val a A[l] transversal al Node principal agregando el bit menos significativo en l .
- Para consultas de tipo 2 , realice la búsqueda binaria en el árbol de Fenwick para obtener el límite inferior.
- Siempre que aparezca una suma de prefijos mayor que K , almacene ese índice y recorra la parte izquierda del árbol de Fenwick. De lo contrario, atraviese la parte derecha del Fenwick Tree ahora, realice una búsqueda binaria .
- Finalmente, imprima el índice requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate and return
// the sum of arr[0..index]
int getSum(int BITree[], int index)
{
int ans = 0;
index += 1;
// Traverse ancestors
// of BITree[index]
while (index > 0)
{
// Update the sum of current
// element of BIT to ans
ans += BITree[index];
// Update index to that
// of the parent node in
// getSum() view by
// subtracting LSB(Least
// Significant Bit)
index -= index & (-index);
}
return ans;
}
// Function to update the Binary Index
// Tree by replacing all ancestors of
// index by their respective sum with val
static void updateBIT(int BITree[], int n,
int index, int val)
{
index = index + 1;
// Traverse all ancestors
// and sum with 'val'.
while (index <= n)
{
// Add 'val' to current
// node of BIT
BITree[index] += val;
// Update index to that
// of the parent node in
// updateBit() view by
// adding LSB(Least
// Significant Bit)
index += index & (-index);
}
}
// Function to construct the Binary
// Indexed Tree for the given array
int* constructBITree(int arr[], int n)
{
// Initialize the
// Binary Indexed Tree
int* BITree = new int[n + 1];
for(int i = 0; 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]);
return BITree;
}
// Function to obtain and return
// the index of lower_bound of k
int getLowerBound(int BITree[], int arr[],
int n, int k)
{
int lb = -1;
int l = 0, r = n - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (getSum(BITree, mid) >= k)
{
r = mid - 1;
lb = mid;
}
else
l = mid + 1;
}
return lb;
}
void performQueries(int A[], int n, int q[][3])
{
// Store the Binary Indexed Tree
int* BITree = constructBITree(A, n);
// Solve each query in Q
for(int i = 0;
i < sizeof(q[0]) / sizeof(int);
i++)
{
int id = q[i][0];
if (id == 1)
{
int idx = q[i][1];
int val = q[i][2];
A[idx] += val;
// Update the values of all
// ancestors of idx
updateBIT(BITree, n, idx, val);
}
else
{
int k = q[i][1];
int lb = getLowerBound(BITree,
A, n, k);
cout << lb << endl;
}
}
}
// Driver Code
int main()
{
int A[] = { 1, 2, 3, 5, 8 };
int n = sizeof(A) / sizeof(int);
int q[][3] = { { 1, 0, 2 },
{ 2, 5, 0 },
{ 1, 3, 5 } };
performQueries(A, n, q);
}
// This code is contributed by jrishabh99
Java
// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
class GFG {
// Function to calculate and return
// the sum of arr[0..index]
static int getSum(int BITree[],
int index)
{
int ans = 0;
index += 1;
// Traverse ancestors
// of BITree[index]
while (index > 0) {
// Update the sum of current
// element of BIT to ans
ans += BITree[index];
// Update index to that
// of the parent node in
// getSum() view by
// subtracting LSB(Least
// Significant Bit)
index -= index & (-index);
}
return ans;
}
// Function to update the Binary Index
// Tree by replacing all ancestors of
// index by their respective sum with val
static void updateBIT(int BITree[],
int n, int index, int val)
{
index = index + 1;
// Traverse all ancestors
// and sum with 'val'.
while (index <= n) {
// Add 'val' to current
// node of BIT
BITree[index] += val;
// Update index to that
// of the parent node in
// updateBit() view by
// adding LSB(Least
// Significant Bit)
index += index & (-index);
}
}
// Function to construct the Binary
// Indexed Tree for the given array
static int[] constructBITree(
int arr[], int n)
{
// Initialize the
// Binary Indexed Tree
int[] BITree = new int[n + 1];
for (int i = 0; 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]);
return BITree;
}
// Function to obtain and return
// the index of lower_bound of k
static int getLowerBound(int BITree[],
int[] arr, int n, int k)
{
int lb = -1;
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (getSum(BITree, mid) >= k) {
r = mid - 1;
lb = mid;
}
else
l = mid + 1;
}
return lb;
}
static void performQueries(int A[], int n, int q[][])
{
// Store the Binary Indexed Tree
int[] BITree = constructBITree(A, n);
// Solve each query in Q
for (int i = 0; i < q.length; i++) {
int id = q[i][0];
if (id == 1) {
int idx = q[i][1];
int val = q[i][2];
A[idx] += val;
// Update the values of all
// ancestors of idx
updateBIT(BITree, n, idx, val);
}
else {
int k = q[i][1];
int lb = getLowerBound(
BITree, A, n, k);
System.out.println(lb);
}
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 2, 3, 5, 8 };
int n = A.length;
int[][] q = { { 1, 0, 2 },
{ 2, 5 },
{ 1, 3, 5 } };
performQueries(A, n, q);
}
}
Python3
# Python3 program to implement # the above approach # Function to calculate and return # the sum of arr[0..index] def getSum(BITree, index): ans = 0 index += 1 # Traverse ancestors # of BITree[index] while (index > 0): # Update the sum of current # element of BIT to ans ans += BITree[index] # Update index to that # of the parent node in # getSum() view by # subtracting LSB(Least # Significant Bit) index -= index & (-index) return ans # Function to update the # Binary Index Tree by # replacing all ancestors # of index by their respective # sum with val def updateBIT(BITree, n, index, val): index = index + 1 # Traverse all ancestors # and sum with 'val'. while (index <= n): # Add 'val' to current # node of BIT BITree[index] += val # Update index to that # of the parent node in # updateBit() view by # adding LSB(Least # Significant Bit) index += index & (-index) # Function to construct the Binary # Indexed Tree for the given array def constructBITree(arr, n): # Initialize the # Binary Indexed Tree BITree = [0] * (n + 1) for i in range(n + 1): BITree[i] = 0 # Store the actual values in # BITree[] using update() for i in range(n): updateBIT(BITree, n, i, arr[i]) return BITree # Function to obtain and return # the index of lower_bound of k def getLowerBound(BITree, arr, n, k): lb = -1 l = 0 r = n - 1 while (l <= r): mid = l + (r - l) // 2 if (getSum(BITree, mid) >= k): r = mid - 1 lb = mid else: l = mid + 1 return lb def performQueries(A, n, q): # Store the Binary Indexed Tree BITree = constructBITree(A, n) # Solve each query in Q for i in range(len(q)): id = q[i][0] if (id == 1): idx = q[i][1] val = q[i][2] A[idx] += val # Update the values of all # ancestors of idx updateBIT(BITree, n, idx, val) else: k = q[i][1] lb = getLowerBound(BITree, A, n, k) print(lb) # Driver Code if __name__ == "__main__": A = [1, 2, 3, 5, 8] n = len(A) q = [[1, 0, 2], [2, 5, 0], [1, 3, 5]] performQueries(A, n, q) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate and return
// the sum of arr[0..index]
static int getSum(int []BITree,
int index)
{
int ans = 0;
index += 1;
// Traverse ancestors
// of BITree[index]
while (index > 0)
{
// Update the sum of current
// element of BIT to ans
ans += BITree[index];
// Update index to that
// of the parent node in
// getSum() view by
// subtracting LSB(Least
// Significant Bit)
index -= index & (-index);
}
return ans;
}
// Function to update the Binary Index
// Tree by replacing all ancestors of
// index by their respective sum with val
static void updateBIT(int []BITree,
int n, int index,
int val)
{
index = index + 1;
// Traverse all ancestors
// and sum with 'val'.
while (index <= n)
{
// Add 'val' to current
// node of BIT
BITree[index] += val;
// Update index to that
// of the parent node in
// updateBit() view by
// adding LSB(Least
// Significant Bit)
index += index & (-index);
}
}
// Function to construct the Binary
// Indexed Tree for the given array
static int[] constructBITree(int []arr,
int n)
{
// Initialize the
// Binary Indexed Tree
int[] BITree = new int[n + 1];
for(int i = 0; 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]);
return BITree;
}
// Function to obtain and return
// the index of lower_bound of k
static int getLowerBound(int []BITree,
int[] arr, int n,
int k)
{
int lb = -1;
int l = 0, r = n - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (getSum(BITree, mid) >= k)
{
r = mid - 1;
lb = mid;
}
else
l = mid + 1;
}
return lb;
}
static void performQueries(int []A, int n,
int [,]q)
{
// Store the Binary Indexed Tree
int[] BITree = constructBITree(A, n);
// Solve each query in Q
for(int i = 0; i < q.GetLength(0); i++)
{
int id = q[i, 0];
if (id == 1)
{
int idx = q[i, 1];
int val = q[i, 2];
A[idx] += val;
// Update the values of all
// ancestors of idx
updateBIT(BITree, n, idx, val);
}
else
{
int k = q[i, 1];
int lb = getLowerBound(BITree,
A, n, k);
Console.WriteLine(lb);
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 1, 2, 3, 5, 8 };
int n = A.Length;
int [,]q = { { 1, 0, 2 },
{ 2, 5, 0 },
{ 1, 3, 5 } };
performQueries(A, n, q);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to calculate and return
// the sum of arr[0..index]
function getSum(BITree, index) {
let ans = 0;
index += 1;
// Traverse ancestors
// of BITree[index]
while (index > 0) {
// Update the sum of current
// element of BIT to ans
ans += BITree[index];
// Update index to that
// of the parent node in
// getSum() view by
// subtracting LSB(Least
// Significant Bit)
index -= index & (-index);
}
return ans;
}
// Function to update the Binary Index
// Tree by replacing all ancestors of
// index by their respective sum with val
function updateBIT(BITree, n, index, val) {
index = index + 1;
// Traverse all ancestors
// and sum with 'val'.
while (index <= n) {
// Add 'val' to current
// node of BIT
BITree[index] += val;
// Update index to that
// of the parent node in
// updateBit() view by
// adding LSB(Least
// Significant Bit)
index += index & (-index);
}
}
// Function to construct the Binary
// Indexed Tree for the given array
function constructBITree(arr, n) {
// Initialize the
// Binary Indexed Tree
let BITree = new Array(n + 1);
for (let i = 0; i <= n; i++)
BITree[i] = 0;
// Store the actual values in
// BITree[] using update()
for (let i = 0; i < n; i++)
updateBIT(BITree, n, i, arr[i]);
return BITree;
}
// Function to obtain and return
// the index of lower_bound of k
function getLowerBound(BITree, arr, n, k) {
let lb = -1;
let l = 0, r = n - 1;
while (l <= r) {
let mid = Math.floor(l + (r - l) / 2);
if (getSum(BITree, mid) >= k) {
r = mid - 1;
lb = mid;
}
else
l = mid + 1;
}
return lb;
}
function performQueries(A, n, q) {
// Store the Binary Indexed Tree
let BITree = constructBITree(A, n);
// Solve each query in Q
for (let i = 0;
i < q.length;
i++) {
let id = q[i][0];
if (id == 1) {
let idx = q[i][1];
let val = q[i][2];
A[idx] += val;
// Update the values of all
// ancestors of idx
updateBIT(BITree, n, idx, val);
}
else {
let k = q[i][1];
let lb = getLowerBound(BITree,
A, n, k);
document.write(lb + "<br>");
}
}
}
// Driver Code
let A = [1, 2, 3, 5, 8];
let n = A.length;
let q = [[1, 0, 2],
[2, 5, 0],
[1, 3, 5]];
performQueries(A, n, q);
// This code is contributed by gfgking
</script>
Producción:
1
Complejidad de tiempo: O(Q*(logN) 2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Ganeshchowdharysadanala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA