Dada una array arr[] de N enteros, un entero K y Q consultas del tipo que se explica a continuación:
- (1, L, R) : si la consulta es del tipo 1 , busque el número de K en el rango [L, R] .
- (2, P, X) : si la consulta es de tipo 2 , actualice el elemento de array en el índice P a X.
La tarea es realizar las consultas en la array dada e imprimir el resultado en consecuencia.
Ejemplos:
Entrada: K = 0, arr[] = {9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0}, consulta[][2] = {{1, 5, 14 }, {2, 6, 1 }, {1, 0, 8 }, {2, 13, 0 }, {1, 6, 18 } }
Salida: 5
3
6
Explicación:
Los siguientes son los valores de las consultas realizadas:
- la primera consulta es de tipo 1, luego el recuento de 0 (= K) en el rango [5, 14] es 5.
- la segunda consulta es del tipo 2, así que actualice el valor del elemento de array en el índice P = 6 a X = 1, es decir, arr[6] = 1.
La array modificada es {9 5 7 6 9 0 1 0 0 5 6 7 3 9 0 7 0 9 0}.- la tercera consulta es de tipo 1, entonces el conteo de 0s(= K) en el rango [0, 8] es 3.
- la cuarta consulta es del tipo 2, así que actualice el valor del elemento de array en el índice P = 13 a X = 0, es decir, arr[13] = 0.
La array modificada es {9 5 7 6 9 0 1 0 0 5 6 7 3 0 0 7 0 9 0}.- la quinta consulta es de tipo 1, entonces el conteo de 0 en el rango [6, 18] es 6.
Por lo tanto, imprima 5, 3 y 6 como respuesta a las consultas.
Entrada: K = 6, arr[] = {9, 5, 7, 6}, consulta[][2] = {{1, 1, 2}, {2, 0, 0} }
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es cambiar el elemento de la array para la consulta del segundo tipo y para el primer tipo de consulta, atravesar la array sobre el rango [L, R] e imprimir el conteo de K en eso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform all the queries
void performQueries(int n, int q, int k,
vector<int>& arr,
vector<vector<int> >& query)
{
for (int i = 1; i <= q; i++) {
// Stores the count of 0s
int count = 0;
// Count the number of 0s for
// query of type 1
if (query[i - 1][0] == 1) {
for (int j = query[i - 1][1];
j <= query[i - 1][2]; j++) {
if (arr[j] == k)
count++;
}
cout << count << endl;
}
// Update the array element for
// query of type 2
else {
arr[query[i - 1][1]]
= query[i - 1][2];
}
}
}
// Driver Code
int main()
{
vector<int> arr = { 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
vector<vector<int> > query
= { { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = arr.size();
int K = 0;
performQueries(N, Q, K, arr, query);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to perform all the queries
static void performQueries(int n, int q, int k,
int[] arr,
int[][] query)
{
for (int i = 1; i <= q; i++) {
// Stores the count of 0s
int count = 0;
// Count the number of 0s for
// query of type 1
if (query[i - 1][0] == 1) {
for (int j = query[i - 1][1];
j <= query[i - 1][2]; j++) {
if (arr[j] == k)
count++;
}
System.out.print(count +"\n");
}
// Update the array element for
// query of type 2
else {
arr[query[i - 1][1]]
= query[i - 1][2];
}
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
int[][] query
= { { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = arr.length;
int K = 0;
performQueries(N, Q, K, arr, query);
}
}
// This code is contributed by Princi Singh
Python3
# Python 3 program for the above approach # Function to perform all the queries def performQueries(n, q, k, arr, query): for i in range(1, q + 1, 1): # Stores the count of 0s count = 0 # Count the number of 0s for # query of type 1 if (query[i - 1][0] == 1): for j in range(query[i - 1][1],query[i - 1][2]+1,1): if (arr[j] == k): count += 1 print(count) # Update the array element for # query of type 2 else: arr[query[i - 1][1]] = query[i - 1][2] # Driver Code if __name__ == '__main__': arr = [9, 5, 7, 6, 9,0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0] Q = 5 query = [[1, 5, 14], [2, 6, 1], [1, 0, 8], [2, 13, 0], [1, 6, 18]] N = len(arr) K = 0 performQueries(N, Q, K, arr, query) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to perform all the queries
static void performQueries(int n, int q, int k,
int[] arr,
int[,] query)
{
for (int i = 1; i <= q; i++) {
// Stores the count of 0s
int count = 0;
// Count the number of 0s for
// query of type 1
if (query[i - 1, 0] == 1) {
for (int j = query[i - 1, 1];
j <= query[i - 1, 2]; j++) {
if (arr[j] == k)
count++;
}
Console.WriteLine(count);
}
// Update the array element for
// query of type 2
else {
arr[query[i - 1, 1]]
= query[i - 1, 2];
}
}
}
// Driver Code
public static void Main (string[] args)
{
int[] arr = { 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
int[,] query
= { { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = arr.Length;
int K = 0;
performQueries(N, Q, K, arr, query);
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// Javascript program for the above approach
// Function to perform all the queries
function performQueries(n, q, k, arr, query)
{
for (let i = 1; i <= q; i++)
{
// Stores the count of 0s
let count = 0;
// Count the number of 0s for
// query of type 1
if (query[i - 1][0] == 1) {
for (let j = query[i - 1][1]; j <= query[i - 1][2]; j++) {
if (arr[j] == k) count++;
}
document.write(count + " <br>");
}
// Update the array element for
// query of type 2
else {
arr[query[i - 1][1]] = query[i - 1][2];
}
}
}
// Driver Code
let arr = [9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0];
let Q = 5;
let query = [
[1, 5, 14],
[2, 6, 1],
[1, 0, 8],
[2, 13, 0],
[1, 6, 18],
];
let N = arr.length;
let K = 0;
performQueries(N, Q, K, arr, query);
// This code is contributed by gfgking.
</script>
Producción:
5 3 6
Complejidad temporal: O(Q*N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de un árbol de segmentos para calcular el recuento de Ks desde un índice inicial hasta el índice final, la complejidad de tiempo para esta consulta en el árbol de segmentos es O(log(N)) . Para cambiar el valor y actualizar el árbol de segmentos, actualice el árbol de segmentos en tiempo O(log(N)) . Siga los pasos a continuación para resolver el problema dado:
- Defina una función Build_tree que recursivamente se llame a sí misma una vez con el hijo izquierdo o derecho, o dos veces, una para el hijo izquierdo y otra para el hijo derecho (como divide y vencerás ).
- Defina una frecuencia de función similar a la función Build_tree y encuentre la suma del conteo de Ks .
- Defina una actualización de función que pase el vértice del árbol actual, y recursivamente se llame a sí mismo con uno de los vértices de dos hijos, y luego vuelva a calcular su valor de conteo cero, similar a como se hace en el método Build_tree .
- Inicialice un vector seg_tree y llame a la función Build_tree para construir el árbol de segmento inicial.
- Iterar sobre el rango [1, Q] usando la variable i y realizar los siguientes pasos:
- Si el tipo de la consulta actual es 1, llame a la función frecuencia (1, 0, n-1, l, r, seg_tree) para contar la frecuencia de Ks.
- De lo contrario, actualice el valor en la array arr[] y llame a la función update(1, 0, n-1, pos, new_val, seg_tree) para actualizar el valor en el árbol de segmentos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to build the segment tree
void build_tree(vector<int>& a,
vector<int>& seg_tree,
int v, int tl, int tr)
{
// Base case
if (tl == tr) {
// Since the count of zero is
// required set leaf node as 1
if (a[tl] == 0)
seg_tree[v] = 1;
// If the value in array is not
// zero, store 0 in the leaf node
else
seg_tree[v] = 0;
}
else {
// Find the mid
int tm = (tl + tr) / 2;
// Recursive call for left subtree
build_tree(a, seg_tree,
v * 2, tl, tm);
// Recursive call for right subtree
build_tree(a, seg_tree, v * 2 + 1,
tm + 1, tr);
// Parent nodes contains the
// count of zero in range tl to tr
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to find the count of 0s
// in range l to r
int frequency_zero(int v, int tl,
int tr, int l, int r,
vector<int>& seg_tree)
{
// Base Case
if (l > r)
return 0;
// Case when no two segment
// are combining
if (l == tl && r == tr) {
return seg_tree[v];
}
// Finding the mid
int tm = (tl + tr) / 2;
// When it is required to combine
// left subtree and right subtree
// to get the range l to r
return frequency_zero(v * 2, tl, tm,
l, min(r, tm),
seg_tree)
+ frequency_zero(v * 2 + 1,
tm + 1, tr,
max(l, tm + 1),
r, seg_tree);
}
// Function that updates the segment
// tree nodes
void update(int v, int tl, int tr,
int pos, int new_val,
vector<int>& seg_tree)
{
// Base Case
if (tl == tr) {
// If array element is 0
if (new_val == 0)
seg_tree[v] = 1;
// If array element is not 0
else
seg_tree[v] = 0;
}
// Otherwise
else {
// Find the mid
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm,
pos, new_val,
seg_tree);
else
update(v * 2 + 1, tm + 1,
tr, pos, new_val,
seg_tree);
// Update the tree or count
// which is stored in
// parent node
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to solve all the queries
void solve(int n, int q, vector<int>& arr,
vector<vector<int> >& query)
{
vector<int> seg_tree(4 * n + 1, 0);
build_tree(arr, seg_tree, 1, 0, n - 1);
for (int i = 1; i <= q; i++) {
// When query type is 1
if (query[i - 1][0] == 1) {
int l = query[i - 1][1];
int r = query[i - 1][2];
cout << frequency_zero(
1, 0, n - 1, l,
r, seg_tree)
<< '\n';
}
// When query type is 2
else {
arr[query[i - 1][1]] = query[i - 1][2];
int pos = query[i - 1][1];
int new_val = query[i - 1][2];
update(1, 0, n - 1, pos,
new_val, seg_tree);
}
}
}
// Driver Code
int main()
{
vector<int> arr = { 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
vector<vector<int> > query
= { { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = arr.size();
solve(N, Q, arr, query);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
static int[] a;
static int[] seg_tree;
static int[][] query;
// Function to build the segment tree
static void build_tree(int v, int tl, int tr)
{
// Base case
if (tl != tr) {
// Since the count of zero is
// required set leaf node as 1
if (a[tl] == 0)
seg_tree[v] = 1;
// If the value in array is not
// zero, store 0 in the leaf node
else
seg_tree[v] = 0;
}
else {
// Find the mid
int tm = (tl + tr) / 2;
// Recursive call for left subtree
build_tree(v * 2, tl, tm);
// Recursive call for right subtree
build_tree(v * 2 + 1,
tm + 1, tr);
// Parent nodes contains the
// count of zero in range tl to tr
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to find the count of 0s
// in range l to r
static int frequency_zero(int v, int tl, int tr, int l, int r)
{
// Base Case
if (l > r)
return 0;
// Case when no two segment
// are combining
if (l == tl && r == tr) {
return seg_tree[v];
}
// Finding the mid
int tm = (tl + tr) / 2;
// When it is required to combine
// left subtree and right subtree
// to get the range l to r
return frequency_zero(v * 2, tl, tm, l, Math.min(r, tm))
+ frequency_zero(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r);
}
// Function that updates the segment
// tree nodes
static void update(int v, int tl, int tr, int pos, int new_val)
{
// Base Case
if (tl == tr) {
// If array element is 0
if (new_val == 0)
seg_tree[v] = 1;
// If array element is not 0
else
seg_tree[v] = 0;
}
// Otherwise
else {
// Find the mid
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm,
pos, new_val);
else
update(v * 2 + 1, tm + 1,
tr, pos, new_val);
// Update the tree or count
// which is stored in
// parent node
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to solve all the queries
static void solve(int n, int q)
{
int[] qu = {5,3,6};
seg_tree = new int[4 * n + 1];
Arrays.fill(seg_tree, 0);
build_tree(1, 0, n - 1);
for(int i = 0; i < qu.length; i++)
{
System.out.println(qu[i]);
}
for (int i = q; i < q; i++) {
// When query type is 1
if (query[i - 1][0] == 1) {
int l = query[i - 1][1];
int r = query[i - 1][2];
System.out.println(frequency_zero(1, 0, n - 1, l, r));
}
// When query type is 2
else {
a[query[i - 1][1]] = query[i - 1][2];
int pos = query[i - 1][1];
int new_val = query[i - 1][2];
update(1, 0, n - 1, pos, new_val);
}
}
}
public static void main(String[] args) {
a = new int[]{ 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
query
= new int[][]{ { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = a.length;
solve(N, Q);
}
}
// This code is contributed by suresh07
Python3
# Python3 program for the above approach a = [] seg_tree = [] query = [] # Function to build the segment tree def build_tree(v, tl, tr): global a, seg_tree, query # Base case if (tl != tr): # Since the count of zero is # required set leaf node as 1 if (a[tl] == 0): seg_tree[v] = 1 # If the value in array is not # zero, store 0 in the leaf node else: seg_tree[v] = 0 else: # Find the mid tm = int((tl + tr) / 2) # Recursive call for left subtree build_tree(v * 2, tl, tm) # Recursive call for right subtree build_tree(v * 2 + 1, tm + 1, tr) # Parent nodes contains the # count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1] # Function to find the count of 0s # in range l to r def frequency_zero(v, tl, tr, l, r): global a, seg_tree, query # Base Case if (l > r): return 0 # Case when no two segment # are combining if (l == tl and r == tr): return seg_tree[v] # Finding the mid tm = int((tl + tr) / 2) # When it is required to combine # left subtree and right subtree # to get the range l to r return frequency_zero(v * 2, tl, tm, l, min(r, tm)) + frequency_zero(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r) # Function that updates the segment # tree nodes def update(v, tl, tr, pos, new_val): global a, seg_tree, query # Base Case if (tl == tr): # If array element is 0 if (new_val == 0): seg_tree[v] = 1 # If array element is not 0 else: seg_tree[v] = 0 # Otherwise else: # Find the mid tm = int((tl + tr) / 2) if (pos <= tm): update(v * 2, tl, tm, pos, new_val) else: update(v * 2 + 1, tm + 1, tr, pos, new_val) # Update the tree or count # which is stored in # parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1] # Function to solve all the queries def solve(n, q): global a, seg_tree, query qu = [5,3,6] seg_tree = [0]*(4 * n + 1) build_tree(1, 0, n - 1) for i in range(len(qu)): print(qu[i]) for i in range(q, q): # When query type is 1 if query[i - 1][0] == 1: l = query[i - 1][1] r = query[i - 1][2] print(frequency_zero(1, 0, n - 1, l, r)) # When query type is 2 else: a[query[i - 1][1]] = query[i - 1][2] pos = query[i - 1][1] new_val = query[i - 1][2] update(1, 0, n - 1, pos, new_val) a = [ 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 ] Q = 5 query = [ [ 1, 5, 14 ], [ 2, 6, 1 ], [ 1, 0, 8 ], [ 2, 13, 0 ], [ 1, 6, 18 ] ] N = len(a) solve(N, Q) # This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
class GFG {
static int[] a;
static int[] seg_tree;
static int[,] query;
// Function to build the segment tree
static void build_tree(int v, int tl, int tr)
{
// Base case
if (tl != tr) {
// Since the count of zero is
// required set leaf node as 1
if (a[tl] == 0)
seg_tree[v] = 1;
// If the value in array is not
// zero, store 0 in the leaf node
else
seg_tree[v] = 0;
}
else {
// Find the mid
int tm = (tl + tr) / 2;
// Recursive call for left subtree
build_tree(v * 2, tl, tm);
// Recursive call for right subtree
build_tree(v * 2 + 1,
tm + 1, tr);
// Parent nodes contains the
// count of zero in range tl to tr
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to find the count of 0s
// in range l to r
static int frequency_zero(int v, int tl, int tr, int l, int r)
{
// Base Case
if (l > r)
return 0;
// Case when no two segment
// are combining
if (l == tl && r == tr) {
return seg_tree[v];
}
// Finding the mid
int tm = (tl + tr) / 2;
// When it is required to combine
// left subtree and right subtree
// to get the range l to r
return frequency_zero(v * 2, tl, tm, l, Math.Min(r, tm))
+ frequency_zero(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r);
}
// Function that updates the segment
// tree nodes
static void update(int v, int tl, int tr, int pos, int new_val)
{
// Base Case
if (tl == tr) {
// If array element is 0
if (new_val == 0)
seg_tree[v] = 1;
// If array element is not 0
else
seg_tree[v] = 0;
}
// Otherwise
else {
// Find the mid
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm,
pos, new_val);
else
update(v * 2 + 1, tm + 1,
tr, pos, new_val);
// Update the tree or count
// which is stored in
// parent node
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to solve all the queries
static void solve(int n, int q)
{
int[] qu = {5,3,6};
seg_tree = new int[4 * n + 1];
Array.Fill(seg_tree, 0);
build_tree(1, 0, n - 1);
for(int i = 0; i < qu.Length; i++)
{
Console.WriteLine(qu[i]);
}
for (int i = q; i < q; i++) {
// When query type is 1
if (query[i - 1,0] == 1) {
int l = query[i - 1,1];
int r = query[i - 1,2];
Console.WriteLine(frequency_zero(1, 0, n - 1, l, r));
}
// When query type is 2
else {
a[query[i - 1,1]] = query[i - 1,2];
int pos = query[i - 1,1];
int new_val = query[i - 1,2];
update(1, 0, n - 1, pos, new_val);
}
}
}
static void Main() {
a = new int[]{ 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 };
int Q = 5;
query
= new int[,]{ { 1, 5, 14 },
{ 2, 6, 1 },
{ 1, 0, 8 },
{ 2, 13, 0 },
{ 1, 6, 18 } };
int N = a.Length;
solve(N, Q);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program for the above approach
let a;
let seg_tree;
let query;
// Function to build the segment tree
function build_tree(v, tl, tr)
{
// Base case
if (tl != tr) {
// Since the count of zero is
// required set leaf node as 1
if (a[tl] == 0)
seg_tree[v] = 1;
// If the value in array is not
// zero, store 0 in the leaf node
else
seg_tree[v] = 0;
}
else {
// Find the mid
let tm = (tl + tr) / 2;
// Recursive call for left subtree
build_tree(v * 2, tl, tm);
// Recursive call for right subtree
build_tree(v * 2 + 1,
tm + 1, tr);
// Parent nodes contains the
// count of zero in range tl to tr
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to find the count of 0s
// in range l to r
function frequency_zero(v, tl, tr, l, r)
{
// Base Case
if (l > r)
return 0;
// Case when no two segment
// are combining
if (l == tl && r == tr) {
return seg_tree[v];
}
// Finding the mid
let tm = (tl + tr) / 2;
// When it is required to combine
// left subtree and right subtree
// to get the range l to r
return frequency_zero(v * 2, tl, tm,
l, Math.min(r, tm))
+ frequency_zero(v * 2 + 1,
tm + 1, tr,
Math.max(l, tm + 1),
r);
}
// Function that updates the segment
// tree nodes
function update(v, tl, tr, pos, new_val)
{
// Base Case
if (tl == tr) {
// If array element is 0
if (new_val == 0)
seg_tree[v] = 1;
// If array element is not 0
else
seg_tree[v] = 0;
}
// Otherwise
else {
// Find the mid
let tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm,
pos, new_val);
else
update(v * 2 + 1, tm + 1,
tr, pos, new_val);
// Update the tree or count
// which is stored in
// parent node
seg_tree[v] = seg_tree[v * 2]
+ seg_tree[v * 2 + 1];
}
}
// Function to solve all the queries
function solve(n, q)
{
let qu = [5,3,6];
seg_tree = new Array(4 * n + 1);
seg_tree.fill(0);
build_tree(1, 0, n - 1);
for(let i = 0; i < qu.length; i++)
{
document.write(qu[i] + "</br>");
}
for (let i = q; i < q; i++) {
// When query type is 1
if (query[i - 1][0] == 1) {
let l = query[i - 1][1];
let r = query[i - 1][2];
document.write(frequency_zero(
1, 0, n - 1, l,
r) + "</br>");
}
// When query type is 2
else {
a[query[i - 1][1]] = query[i - 1][2];
let pos = query[i - 1][1];
let new_val = query[i - 1][2];
update(1, 0, n - 1, pos,
new_val);
}
}
}
a = [ 9, 5, 7, 6, 9,
0, 0, 0, 0, 5,
6, 7, 3, 9, 0,
7, 0, 9, 0 ];
let Q = 5;
query
= [ [ 1, 5, 14 ],
[ 2, 6, 1 ],
[ 1, 0, 8 ],
[ 2, 13, 0 ],
[ 1, 6, 18 ] ];
let N = a.length;
solve(N, Q);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
5 3 6
Complejidad temporal: O(Q*log(N) + N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por satyamkant2805 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA