Consultas para encontrar el límite inferior de K de Prefix Sum Array con actualizaciones usando Fenwick Tree

Dada una array A[ ] que consta de enteros no negativos y una array Q[ ][ ] que consta de consultas de los siguientes dos tipos:

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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *