Consultas para calcular la suma de los cuadrados de los valores ASCII de los caracteres de una substring con actualizaciones

Dada una string S de longitud N y una array 2D de strings Q[][] que consta de M consultas del siguiente tipo:

  • Consulta («U», «I», «X»): actualice el carácter en el índice I con el carácter X .
  • Query(“S”, “L”, “R”): Imprime la suma de los cuadrados de la posición de los caracteres en la substring {S[L], …., S[R]} según los alfabetos ingleses.

Ejemplos:

Entrada: S = “geeksforgeeks”, Q[][] = {{“S”, “0”, “2”}, {“S”, “1”, “2”}, {“U”, “1 ”, “a”}, {“S”, “0”, “2”}, {“S”, “4”, “5”}}
Salida: 
99
50
75
397
Explicación:
Para Consulta(“S”, “0”, “2”) , suma de cuadrados de las posiciones de los caracteres en la substring “gee” = 7*7 + 5*5 + 5*5 = 99.
Para Consulta(“S”, “1”, “2”) , suma de cuadrados de las posiciones del carácter en la substring “ee” = 5*5 + 5*5 = 50.
Para Query(“U”, “1”, “a”): Reemplazando S[ 1] por ‘a’ modifica S a «gaeksforgeeks».
Para Query(“S”, “0”, “2”) , suma de cuadrados de las posiciones de los caracteres en la substring “gae” = 7*7 + 1*1 + 5*5 = 75.
ParaQuery(“S”, “4”, “5”) , suma de cuadrados de las posiciones de los caracteres en la substring “ks” = 19*19 + 36 = 397

Entrada: S = “geeksforgeeks”, Q[][] = {{“S”, “1”, “2”}}
Salida: 50

Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array Q[][] para cada consulta y para consultas de tipo ‘S’ , simplemente recorrer la substring {S[L], …, S[R]} y imprime la suma de los cuadrados de las posiciones de los caracteres en los alfabetos ingleses. En cada iteración para realizar la consulta de tipo ‘U’ , simplemente asigne X a S[I]. 

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la estructura de datos del árbol de segmentos . Siga los pasos a continuación para resolver el problema:

  • Inicialice un árbol de segmentos, digamos tree[] , donde cada Node almacena la suma de los cuadrados de la posición de los caracteres en los alfabetos ingleses en su subárbol.
  • Para Consulta(“U”, “I”, “X”) , defina una función de actualización, similar a la función de actualización de las consultas de rango de suma . Actualice S[i] = X y luego llame a la función update() para actualizar el árbol de segmentos.
  • Para Query(“S”, “L”, “R”) , defina una función query() , similar a sum range query y luego, imprima la suma obtenida llamando a la función query() para la substring {S[L] , …., S[R]} .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node
// of a Segment Tree
struct treeNode {
    int square_sum;
};
 
// Function to construct the Segment Tree
void buildTree(string s, treeNode* tree,
               int start, int end,
               int treeNode)
{
    // If start and end are equal
    if (start == end) {
 
        // Assign squares of positions
        // of the characters
        tree[treeNode].square_sum
            = pow(s[start] - 'a' + 1, 2);
 
        return;
    }
 
    // Stores the mid value of
    // the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // Recursive call to left subtree
    buildTree(s, tree, start,
              mid, 2 * treeNode);
 
    // Recursive call to right subtree
    buildTree(s, tree, mid + 1,
              end, 1 + 2 * treeNode);
 
    // Update the current node
    tree[treeNode].square_sum
        = tree[(2 * treeNode)].square_sum
          + tree[(2 * treeNode) + 1].square_sum;
}
 
// Function to perform the queries of type 2
int querySquareSum(treeNode* tree, int start,
                   int end, int treeNode,
                   int l, int r)
{
    // No overlap
    if ((l > end) || (r < start)) {
        return 0;
    }
 
    // If l <= start and r >= end
    if ((l <= start) && (r >= end)) {
 
        // Return the value of treeNode
        return tree[treeNode].square_sum;
    }
 
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // Function call to left subtree
    int X = querySquareSum(tree, start,
                           mid, 2 * treeNode,
                           l, r);
 
    // Function call to right subtree
    int Y = +querySquareSum(tree, mid + 1, end,
                            1 + 2 * treeNode, l, r);
 
    // Return the sum of X and Y
    return X + Y;
}
 
// Function to perform update
// queries on a Segment Tree
void updateTree(string s, treeNode* tree,
                int start, int end,
                int treeNode, int idx, char X)
{
    // If start is equal to end
    // and idx is equal to start
    if ((start == end) && (idx == start)) {
 
        // Base Case
        s[idx] = X;
        tree[treeNode].square_sum
            = pow(X - 'a' + 1, 2);
 
        return;
    }
 
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // If idx <=  mid
    if (idx <= mid) {
 
        // Function call to left subtree
        updateTree(s, tree, start, mid,
                   (2 * treeNode), idx, X);
    }
 
    // Otherwise
    else {
 
        // Function call to the right subtree
        updateTree(s, tree, mid + 1, end,
                   (2 * treeNode) + 1, idx, X);
    }
 
    // Update the current node
    tree[treeNode].square_sum
        = tree[(2 * treeNode)].square_sum
          + tree[(2 * treeNode) + 1].square_sum;
}
 
// Function to perform the given queries
void PerformQuery(string S,
                  vector<vector<string> > Q)
{
    int n = S.size();
 
    // Stores the segment tree
    treeNode* tree = new treeNode[(4 * n) + 1];
 
    // Traverse the segment tree
    for (int i = 0; i <= (4 * n); i = i + 1) {
 
        // Assign 0 to each node
        tree[i].square_sum = 0;
    }
 
    // Builds segment tree
    buildTree(S, tree, 0, n - 1, 1);
 
    // Traverse the query array Q[][]
    for (int i = 0; i < Q.size(); i++) {
 
        // If query is of type S
        if (Q[i][0] == "S") {
 
            // Stores the left boundary
            int L = stoi(Q[i][1]);
 
            // Stores the right boundary
            int R = stoi(Q[i][2]);
 
            // Prints the sum of squares of the
            // alphabetic positions of the characters
            cout << querySquareSum(tree, 0,
                                   n - 1, 1, L, R)
                 << endl;
        }
 
        // Otherwise
        else if (Q[i][0] == "U") {
 
            // Stores the index of the
            // character to be updated
            int I = stoi(Q[i][1]);
 
            // Update the segment tree
            updateTree(S, tree, 0, n - 1,
                       1, I, Q[i][2][0]);
        }
    }
}
 
// Driver Code
int main()
{
    // Input
    string S = "geeksforgeeks";
    vector<vector<string> > Q = { { "S", "0", "2" },
                                  { "S", "1", "2" },
                                  { "U", "1", "a" },
                                  { "S", "0", "2" },
                                  { "S", "4", "5" } };
    // Function call
    PerformQuery(S, Q);
}

Java

// Java implementation of
// the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Structure of a node
// of a Segment Tree
static class treeNode
{
    int square_sum;
 
    treeNode(int square_sum)
    {
        this.square_sum = square_sum;
    }
};
 
// Function to construct the Segment Tree
static void buildTree(char s[], treeNode tree[],
                      int start, int end, int treenode)
{
     
    // If start and end are equal
    if (start == end)
    {
         
        // Assign squares of positions
        // of the characters
        tree[treenode].square_sum = (int)Math.pow(
            s[start] - 'a' + 1, 2);
 
        return;
    }
 
    // Stores the mid value of
    // the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // Recursive call to left subtree
    buildTree(s, tree, start, mid, 2 * treenode);
 
    // Recursive call to right subtree
    buildTree(s, tree, mid + 1, end, 1 + 2 * treenode);
 
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
 
// Function to perform the queries of type 2
static int querySquareSum(treeNode tree[], int start,
                          int end, int treenode, int l,
                          int r)
{
     
    // No overlap
    if ((l > end) || (r < start))
    {
        return 0;
    }
 
    // If l <= start and r >= end
    if ((l <= start) && (r >= end))
    {
 
        // Return the value of treeNode
        return tree[treenode].square_sum;
    }
 
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // Function call to left subtree
    int X = querySquareSum(tree, start, mid,
                           2 * treenode, l, r);
 
    // Function call to right subtree
    int Y = +querySquareSum(tree, mid + 1, end,
                            1 + 2 * treenode, l, r);
 
    // Return the sum of X and Y
    return X + Y;
}
 
// Function to perform update
// queries on a Segment Tree
static void updateTree(char s[], treeNode tree[],
                       int start, int end, int treenode,
                       int idx, char X)
{
     
    // If start is equal to end
    // and idx is equal to start
    if ((start == end) && (idx == start))
    {
         
        // Base Case
        s[idx] = X;
        tree[treenode].square_sum = (int)Math.pow(
            X - 'a' + 1, 2);
 
        return;
    }
 
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
 
    // If idx <=  mid
    if (idx <= mid)
    {
         
        // Function call to left subtree
        updateTree(s, tree, start, mid, (2 * treenode),
                   idx, X);
    }
 
    // Otherwise
    else
    {
 
        // Function call to the right subtree
        updateTree(s, tree, mid + 1, end,
                 (2 * treenode) + 1, idx, X);
    }
 
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
 
// Function to perform the given queries
static void PerformQuery(String S, String Q[][])
{
    int n = S.length();
 
    // Stores the segment tree
    treeNode tree[] = new treeNode[(4 * n) + 1];
 
    // Traverse the segment tree
    for(int i = 0; i <= (4 * n); i = i + 1)
    {
         
        // Assign 0 to each node
        tree[i] = new treeNode(0);
    }
 
    char s[] = S.toCharArray();
 
    // Builds segment tree
    buildTree(s, tree, 0, n - 1, 1);
 
    // Traverse the query array Q[][]
    for(int i = 0; i < Q.length; i++)
    {
         
        // If query is of type S
        if (Q[i][0] == "S")
        {
             
            // Stores the left boundary
            int L = Integer.parseInt(Q[i][1]);
 
            // Stores the right boundary
            int R = Integer.parseInt(Q[i][2]);
 
            // Prints the sum of squares of the
            // alphabetic positions of the characters
            System.out.println(querySquareSum(
                tree, 0, n - 1, 1, L, R));
        }
 
        // Otherwise
        else if (Q[i][0] == "U")
        {
             
            // Stores the index of the
            // character to be updated
            int I = Integer.parseInt(Q[i][1]);
 
            // Update the segment tree
            updateTree(s, tree, 0, n - 1, 1, I,
                       Q[i][2].charAt(0));
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Input
    String S = "geeksforgeeks";
    String Q[][] = { { "S", "0", "2" },
                     { "S", "1", "2" },
                     { "U", "1", "a" },
                     { "S", "0", "2" },
                     { "S", "4", "5" } };
    // Function call
    PerformQuery(S, Q);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 implementation of
# the above approach
 
# Structure of a node
# of a Segment Tree
class treeNode:
     
    def __init__(self, x):
         
        self.square_sum = x
 
# Function to construct the Segment Tree
def buildTree(s, tree, start, end, treeNode):
     
    # If start and end are equa
    if (start == end):
 
        # Assign squares of positions
        # of the characters
        tree[treeNode].square_sum = pow(ord(s[start]) -
                                        ord('a') + 1, 2)
 
        return
 
    # Stores the mid value of
    # the range [start, end]
    mid = start + ((end - start) // 2)
 
    # Recursive call to left subtree
    buildTree(s, tree, start, mid, 2 * treeNode)
 
    # Recursive call to right subtree
    buildTree(s, tree, mid + 1, end,
                         1 + 2 * treeNode)
 
    # Update the current node
    tree[treeNode].square_sum = (tree[(2 * treeNode)].square_sum +
                                 tree[(2 * treeNode) + 1].square_sum)
 
# Function to perform the queries of type 2
def querySquareSum(tree, start, end, treeNode, l, r):
     
    # No overlap
    if ((l > end) or (r < start)):
        return 0
 
    # If l <= start and r >= end
    if ((l <= start) and (r >= end)):
         
        # Return the value of treeNode
        return tree[treeNode].square_sum
 
    # Calculate middle of the range [start, end]
    mid = start + ((end - start) // 2)
 
    # Function call to left subtree
    X = querySquareSum(tree, start, mid,
                       2 * treeNode, l, r)
 
    # Function call to right subtree
    Y = +querySquareSum(tree, mid + 1, end,
                                1 + 2 * treeNode, l, r)
 
    # Return the sum of X and Y
    return X + Y
 
# Function to perform update
# queries on a Segment Tree
def updateTree(s, tree, start, end, treeNode, idx, X):
     
    # If start is equal to end
    # and idx is equal to start
    if ((start == end) and (idx == start)):
 
        # Base Case
        s[idx] = X
        tree[treeNode].square_sum = pow(ord(X) -
                                       ord('a') + 1, 2)
        return
 
    # Calculate middle of the range [start, end]
    mid = start + ((end - start) // 2)
 
    # If idx <=  mid
    if (idx <= mid):
         
        # Function call to left subtree
        updateTree(s, tree, start, mid,
                  (2 * treeNode), idx, X)
                   
    # Otherwise
    else:
 
        # Function call to the right subtree
        updateTree(s, tree, mid + 1, end,
                  (2 * treeNode) + 1, idx, X)
 
    # Update the current node
    tree[treeNode].square_sum = (tree[(2 * treeNode)].square_sum +
                                 tree[(2 * treeNode) + 1].square_sum)
 
# Function to perform the given queries
def PerformQuery(S, Q):
     
    n = len(S)
 
    # Stores the segment tree
    tree = [treeNode(0) for i in range((4 * n) + 1)]
 
    # Traverse the segment tree
    for i in range(4 * n + 1):
         
        # Assign 0 to each node
        tree[i].square_sum = 0
 
    # Builds segment tree
    buildTree(S, tree, 0, n - 1, 1)
 
    # Traverse the query array Q[][]
    for i in range(len(Q)):
         
        # If query is of type S
        if (Q[i][0] == "S"):
             
            # Stores the left boundary
            L = int(Q[i][1])
 
            # Stores the right boundary
            R = int(Q[i][2])
 
            # Prints the sum of squares of the
            # alphabetic positions of the characters
            print(querySquareSum(tree, 0, n - 1,
                                 1, L, R))
 
        # Otherwise
        elif (Q[i][0] == "U"):
 
            # Stores the index of the
            # character to be updated
            I = int(Q[i][1])
 
            # Update the segment tree
            updateTree(S, tree, 0, n - 1,
                       1, I, Q[i][2][0])
 
# Driver Code
if __name__ == '__main__':
     
    # Input
    S = "geeksforgeeks"
    Q = [ [ "S", "0", "2" ],
          [ "S", "1", "2" ],
          [ "U", "1", "a" ],
          [ "S", "0", "2" ],
          [ "S", "4", "5" ] ]
           
    # Function call
    PerformQuery([i for i in S], Q)
 
# This code is contributed by mohit kumar 29

C#

using System;
 
public class treeNode
{
    public int square_sum;
  
    public treeNode(int square_sum)
    {
        this.square_sum = square_sum;
    }
};
 
public class GFG{
     
    // Function to construct the Segment Tree
static void buildTree(char[] s, treeNode[] tree,
                      int start, int end, int treenode)
{
      
    // If start and end are equal
    if (start == end)
    {
          
        // Assign squares of positions
        // of the characters
        tree[treenode].square_sum = (int)Math.Pow(
            s[start] - 'a' + 1, 2);
  
        return;
    }
  
    // Stores the mid value of
    // the range [start, end]
    int mid = start + ((end - start) / 2);
  
    // Recursive call to left subtree
    buildTree(s, tree, start, mid, 2 * treenode);
  
    // Recursive call to right subtree
    buildTree(s, tree, mid + 1, end, 1 + 2 * treenode);
  
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
  
// Function to perform the queries of type 2
static int querySquareSum(treeNode[] tree, int start,
                          int end, int treenode, int l,
                          int r)
{
      
    // No overlap
    if ((l > end) || (r < start))
    {
        return 0;
    }
  
    // If l <= start and r >= end
    if ((l <= start) && (r >= end))
    {
  
        // Return the value of treeNode
        return tree[treenode].square_sum;
    }
  
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
  
    // Function call to left subtree
    int X = querySquareSum(tree, start, mid,
                           2 * treenode, l, r);
  
    // Function call to right subtree
    int Y = +querySquareSum(tree, mid + 1, end,
                            1 + 2 * treenode, l, r);
  
    // Return the sum of X and Y
    return X + Y;
}
  
// Function to perform update
// queries on a Segment Tree
static void updateTree(char[] s, treeNode[] tree,
                       int start, int end, int treenode,
                       int idx, char X)
{
      
    // If start is equal to end
    // and idx is equal to start
    if ((start == end) && (idx == start))
    {
          
        // Base Case
        s[idx] = X;
        tree[treenode].square_sum = (int)Math.Pow(
            X - 'a' + 1, 2);
  
        return;
    }
  
    // Calculate middle of the range [start, end]
    int mid = start + ((end - start) / 2);
  
    // If idx <=  mid
    if (idx <= mid)
    {
          
        // Function call to left subtree
        updateTree(s, tree, start, mid, (2 * treenode),
                   idx, X);
    }
  
    // Otherwise
    else
    {
  
        // Function call to the right subtree
        updateTree(s, tree, mid + 1, end,
                 (2 * treenode) + 1, idx, X);
    }
  
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
  
// Function to perform the given queries
static void PerformQuery(String S, String[,] Q)
{
    int n = S.Length;
  
    // Stores the segment tree
    treeNode[] tree = new treeNode[(4 * n) + 1];
  
    // Traverse the segment tree
    for(int i = 0; i <= (4 * n); i = i + 1)
    {
          
        // Assign 0 to each node
        tree[i] = new treeNode(0);
    }
  
    char[] s = S.ToCharArray();
  
    // Builds segment tree
    buildTree(s, tree, 0, n - 1, 1);
  
    // Traverse the query array Q[][]
    for(int i = 0; i < Q.GetLength(0); i++)
    {
          
        // If query is of type S
        if (Q[i,0] == "S")
        {
              
            // Stores the left boundary
            int L = Int32.Parse(Q[i,1]);
  
            // Stores the right boundary
            int R = Int32.Parse(Q[i,2]);
  
            // Prints the sum of squares of the
            // alphabetic positions of the characters
            Console.WriteLine(querySquareSum(
                tree, 0, n - 1, 1, L, R));
        }
  
        // Otherwise
        else if (Q[i,0] == "U")
        {
              
            // Stores the index of the
            // character to be updated
            int I = Int32.Parse(Q[i,1]);
  
            // Update the segment tree
            updateTree(s, tree, 0, n - 1, 1, I,
                       Q[i,2][0]);
        }
    }
}
  
// Driver Code
     
    static public void Main (){
         
        // Input
    string S = "geeksforgeeks";
    string[,] Q = { { "S", "0", "2" },
                     { "S", "1", "2" },
                     { "U", "1", "a" },
                     { "S", "0", "2" },
                     { "S", "4", "5" } };
    // Function call
    PerformQuery(S, Q);
         
    }
}
 
// This code is contributed by unknown2108.

Javascript

<script>
// Javascript implementation of
// the above approach
 
// Structure of a node
// of a Segment Tree
class treeNode
{
    constructor( square_sum)
    {
        this.square_sum = square_sum;
    }
}
 
// Function to construct the Segment Tree
function buildTree(s,tree,start,end,treenode)
{
    // If start and end are equal
    if (start == end)
    {
          
        // Assign squares of positions
        // of the characters
        tree[treenode].square_sum = Math.pow(
            s[start].charCodeAt(0) - 'a'.charCodeAt(0) + 1, 2);
  
        return;
    }
  
    // Stores the mid value of
    // the range [start, end]
    let mid = start + Math.floor((end - start) / 2);
  
    // Recursive call to left subtree
    buildTree(s, tree, start, mid, 2 * treenode);
  
    // Recursive call to right subtree
    buildTree(s, tree, mid + 1, end, 1 + 2 * treenode);
  
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
 
// Function to perform the queries of type 2
function  querySquareSum(tree,start,end,treenode,l,r)
{
    // No overlap
    if ((l > end) || (r < start))
    {
        return 0;
    }
  
    // If l <= start and r >= end
    if ((l <= start) && (r >= end))
    {
  
        // Return the value of treeNode
        return tree[treenode].square_sum;
    }
  
    // Calculate middle of the range [start, end]
    let mid = start + Math.floor((end - start) / 2);
  
    // Function call to left subtree
    let X = querySquareSum(tree, start, mid,
                           2 * treenode, l, r);
  
    // Function call to right subtree
    let Y = +querySquareSum(tree, mid + 1, end,
                            1 + 2 * treenode, l, r);
  
    // Return the sum of X and Y
    return X + Y;
}
 
// Function to perform update
// queries on a Segment Tree
function updateTree(s,tree,start,end,treenode,idx,X)
{
    // If start is equal to end
    // and idx is equal to start
    if ((start == end) && (idx == start))
    {
          
        // Base Case
        s[idx] = X;
        tree[treenode].square_sum = Math.pow(
            X.charCodeAt(0) - 'a'.charCodeAt(0) + 1, 2);
  
        return;
    }
  
    // Calculate middle of the range [start, end]
    let mid = start + Math.floor((end - start) / 2);
  
    // If idx <=  mid
    if (idx <= mid)
    {
          
        // Function call to left subtree
        updateTree(s, tree, start, mid, (2 * treenode),
                   idx, X);
    }
  
    // Otherwise
    else
    {
  
        // Function call to the right subtree
        updateTree(s, tree, mid + 1, end,
                 (2 * treenode) + 1, idx, X);
    }
  
    // Update the current node
    tree[treenode].square_sum = tree[(2 * treenode)].square_sum +
                                tree[(2 * treenode) + 1].square_sum;
}
 
// Function to perform the given queries
function PerformQuery(S,Q)
{
     let n = S.length;
  
    // Stores the segment tree
    let tree = new Array((4 * n) + 1);
  
    // Traverse the segment tree
    for(let i = 0; i <= (4 * n); i = i + 1)
    {
          
        // Assign 0 to each node
        tree[i] = new treeNode(0);
    }
  
    let s = S.split("");
  
    // Builds segment tree
    buildTree(s, tree, 0, n - 1, 1);
  
    // Traverse the query array Q[][]
    for(let i = 0; i < Q.length; i++)
    {
          
        // If query is of type S
        if (Q[i][0] == "S")
        {
              
            // Stores the left boundary
            let L = parseInt(Q[i][1]);
  
            // Stores the right boundary
            let R = parseInt(Q[i][2]);
  
            // Prints the sum of squares of the
            // alphabetic positions of the characters
            document.write(querySquareSum(
                tree, 0, n - 1, 1, L, R)+"<br>");
        }
  
        // Otherwise
        else if (Q[i][0] == "U")
        {
              
            // Stores the index of the
            // character to be updated
            let I = parseInt(Q[i][1]);
  
            // Update the segment tree
            updateTree(s, tree, 0, n - 1, 1, I,
                       Q[i][2][0]);
        }
    }
}
 
// Driver Code
let S = "geeksforgeeks";
 
let Q=[[ "S", "0", "2" ],
                     [ "S", "1", "2" ],
                     [ "U", "1", "a" ],
                     [ "S", "0", "2" ],
                     [ "S", "4", "5" ]]
// Function call
PerformQuery(S, Q);
 
// This code is contributed by patel2127
</script>
Producción: 

99
50
75
397

 

Complejidad de tiempo: O((N + M) * log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por saivamshik24 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 *