Dada una array arr[] de tamaño N y una array 2D Q[][] , que consta de consultas de los siguientes dos tipos:
- 1 X Val: Actualizar arr[X] = Val .
- 2 LR: encuentre la suma de los elementos de la array con signos alternos en el rango [L, R] .
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 4 }, Q[][] = { { 2, 0, 3 }, { 1, 1, 5 }, { 2, 1, 2 } }
Salida: – 2 2
Explicación:
Consulta1: Imprimir (arr[0] – arr[1] + arr[2] – arr[3]) = 1 – 2 + 3 – 4 = -2
Consulta2: Actualizar arr[1] a 5 modifica arr [] a { 1, 5, 3, 4 }
Consulta 3: Imprimir (arr[1] – arr[2]) = 5 – 3 = 2Entrada: arr[] = { 4, 2, 6, 1, 8, 9, 2}, Q = { { 2, 1, 4 }, { 1, 3, 4 }, { 2, 0, 3 } }
Salida : -11 5
Enfoque: El problema se puede resolver utilizando Segment Tree . La idea es recorrer la array y verificar si el índice del elemento de la array es negativo y luego multiplicar los elementos de la array por -1 . Siga los pasos a continuación para resolver el problema:
- Recorra la array arr[] usando la variable i y verifique si el índice i es impar o no. Si se determina que es cierto, actualice arr[i] = -Val .
- Para consultas de tipo 1, X, Val , verifique si X es par o no. Si se determina que es cierto, actualice arr[X] = Val usando el árbol de segmentos .
- De lo contrario, actualice arr[X] = -Val utilizando el árbol de segmentos.
- Para consultas de tipo 2 LR: , verifique si L es par o no. Si se determina que es cierto, imprima la suma de los elementos de la array en el rango [L, R] utilizando el árbol de segmentos .
- De lo contrario, encuentre la suma de los elementos de la array en el rango [L, R] utilizando el árbol de segmentos e imprima la suma obtenida multiplicando por -1 .
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 build the segment tree
void build(int tree[], int arr[], int start,
int end, int index)
{
// If current node is a leaf node
// of the segment tree
if (start == end) {
if (start % 2 == 0) {
// Update tree[index]
tree[index] = arr[start];
}
else {
// Update tree[index]
tree[index] = -arr[start];
}
return;
}
// Divide the segment tree
int mid = start + (end - start) / 2;
// Update on L segment tree
build(tree, arr, start, mid,
2 * index + 1);
// Update on R segment tree
build(tree, arr, mid + 1, end,
2 * index + 2);
// Find the sum from L subtree
// and R subtree
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to update elements at index pos
// by val in the segment tree
void update(int tree[], int index, int start,
int end, int pos, int val)
{
// If current node is a leaf node
if (start == end) {
// If current index is even
if (start % 2 == 0) {
// Update tree[index]
tree[index] = val;
}
else {
// Update tree[index]
tree[index] = -val;
}
return;
}
// Divide the segment tree elements
// into L and R subtree
int mid = start + (end - start) / 2;
// If element lies in L subtree
if (mid >= pos) {
update(tree, 2 * index + 1, start,
mid, pos, val);
}
else {
update(tree, 2 * index + 2, mid + 1,
end, pos, val);
}
// Update tree[index]
tree[index]
= tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to find the sum of array elements
// in the range [L, R]
int FindSum(int tree[], int start, int end,
int L, int R, int index)
{
// If start and end not lies in
// the range [L, R]
if (L > end || R < start) {
return 0;
}
// If start and end comleately lies
// in the range [L, R]
if (L <= start && R >= end) {
return tree[index];
}
int mid = start + (end - start) / 2;
// Stores sum from left subtree
int X = FindSum(tree, start, mid, L,
R, 2 * index + 1);
// Stores sum from right subtree
int Y = FindSum(tree, mid + 1, end, L,
R, 2 * index + 2);
return X + Y;
}
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
int tree[4 * N + 5] = { 0 };
build(tree, arr, 0, N - 1, 0);
int Q[][3] = { { 2, 0, 3 }, { 1, 1, 5 }, { 2, 1, 2 } };
int cntQuey = 3;
for (int i = 0; i < cntQuey; i++) {
if (Q[i][0] == 1) {
update(tree, 0, 0, N - 1,
Q[i][1], Q[i][2]);
}
else {
if (Q[i][1] % 2 == 0) {
cout << FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0)
<< " ";
}
else {
cout << -FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0)
<< " ";
}
}
}
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to build the segment tree
static void build(int tree[], int arr[], int start,
int end, int index)
{
// If current node is a leaf node
// of the segment tree
if (start == end) {
if (start % 2 == 0) {
// Update tree[index]
tree[index] = arr[start];
}
else {
// Update tree[index]
tree[index] = -arr[start];
}
return;
}
// Divide the segment tree
int mid = start + (end - start) / 2;
// Update on L segment tree
build(tree, arr, start, mid,
2 * index + 1);
// Update on R segment tree
build(tree, arr, mid + 1, end,
2 * index + 2);
// Find the sum from L subtree
// and R subtree
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to update elements at index pos
// by val in the segment tree
static void update(int tree[], int index, int start,
int end, int pos, int val)
{
// If current node is a leaf node
if (start == end) {
// If current index is even
if (start % 2 == 0) {
// Update tree[index]
tree[index] = val;
}
else {
// Update tree[index]
tree[index] = -val;
}
return;
}
// Divide the segment tree elements
// into L and R subtree
int mid = start + (end - start) / 2;
// If element lies in L subtree
if (mid >= pos)
{
update(tree, 2 * index + 1, start,
mid, pos, val);
}
else
{
update(tree, 2 * index + 2, mid + 1,
end, pos, val);
}
// Update tree[index]
tree[index]
= tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to find the sum of array elements
// in the range [L, R]
static int FindSum(int tree[], int start, int end,
int L, int R, int index)
{
// If start and end not lies in
// the range [L, R]
if (L > end || R < start)
{
return 0;
}
// If start and end comleately lies
// in the range [L, R]
if (L <= start && R >= end)
{
return tree[index];
}
int mid = start + (end - start) / 2;
// Stores sum from left subtree
int X = FindSum(tree, start, mid, L,
R, 2 * index + 1);
// Stores sum from right subtree
int Y = FindSum(tree, mid + 1, end, L,
R, 2 * index + 2);
return X + Y;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
int tree[] = new int[4 * N + 5];
Arrays.fill(tree, 0);
build(tree, arr, 0, N - 1, 0);
int Q[][] = { { 2, 0, 3 }, { 1, 1, 5 }, { 2, 1, 2 } };
int cntQuey = 3;
for (int i = 0; i < cntQuey; i++)
{
if (Q[i][0] == 1)
{
update(tree, 0, 0, N - 1,
Q[i][1], Q[i][2]);
}
else {
if (Q[i][1] % 2 == 0)
{
System.out.print(FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0) + " ");
}
else
{
System.out.print(-FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0)+ " ");
}
}
}
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program to implement # the above approach # Function to build the segment tree def build(tree, arr, start, end, index): # If current node is a leaf node # of the segment tree if (start == end): if (start % 2 == 0): # Update tree[index] tree[index] = arr[start] else: # Update tree[index] tree[index] = -arr[start] return # Divide the segment tree mid = start + (end - start) // 2 # Update on L segment tree build(tree, arr, start, mid, 2 * index + 1) # Update on R segment tree build(tree, arr, mid + 1, end, 2 * index + 2) # Find the sum from L subtree # and R subtree tree[index] = tree[2 * index + 1] + tree[2 * index + 2] # Function to update elements at index pos # by val in the segment tree def update(tree, index, start, end, pos, val): # If current node is a leaf node if (start == end): # If current index is even if (start % 2 == 0): # Update tree[index] tree[index] = val else: # Update tree[index] tree[index] = -val return # Divide the segment tree elements # into L and R subtree mid = start + (end - start) // 2 # If element lies in L subtree if (mid >= pos): update(tree, 2 * index + 1, start, mid, pos, val) else: update(tree, 2 * index + 2, mid + 1, end, pos, val) # Update tree[index] tree[index] = tree[2 * index + 1] + tree[2 * index + 2] # Function to find the sum of array elements # in the range [L, R] def FindSum(tree, start, end, L, R, index): # If start and end not lies in # the range [L, R] if (L > end or R < start): return 0 #If start and end comleately lies #in the range [L, R] if (L <= start and R >= end): return tree[index] mid = start + (end - start) // 2 # Stores sum from left subtree X = FindSum(tree, start, mid, L, R, 2 * index + 1) # Stores sum from right subtree Y = FindSum(tree, mid + 1, end, L, R, 2 * index + 2) return X + Y # Driver code if __name__ == '__main__': arr = [1, 2, 3, 4] N = len(arr) tree = [0 for i in range(4 * N + 5)] build(tree, arr, 0, N - 1, 0) Q = [ [ 2, 0, 3 ], [ 1, 1, 5 ], [ 2, 1, 2 ] ] cntQuey = 3 for i in range(cntQuey): if (Q[i][0] == 1): update(tree, 0, 0, N - 1, Q[i][1], Q[i][2]) else: if (Q[i][1] % 2 == 0): print(FindSum(tree, 0, N - 1, Q[i][1], Q[i][2], 0),end=" ") else: print(-FindSum(tree, 0, N - 1, Q[i][1], Q[i][2], 0),end=" ") # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to build the segment tree
static void build(int[] tree, int[] arr, int start,
int end, int index)
{
// If current node is a leaf node
// of the segment tree
if (start == end)
{
if (start % 2 == 0)
{
// Update tree[index]
tree[index] = arr[start];
}
else
{
// Update tree[index]
tree[index] = -arr[start];
}
return;
}
// Divide the segment tree
int mid = start + (end - start) / 2;
// Update on L segment tree
build(tree, arr, start, mid,
2 * index + 1);
// Update on R segment tree
build(tree, arr, mid + 1, end,
2 * index + 2);
// Find the sum from L subtree
// and R subtree
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to update elements at index pos
// by val in the segment tree
static void update(int[] tree, int index, int start,
int end, int pos, int val)
{
// If current node is a leaf node
if (start == end)
{
// If current index is even
if (start % 2 == 0)
{
// Update tree[index]
tree[index] = val;
}
else
{
// Update tree[index]
tree[index] = -val;
}
return;
}
// Divide the segment tree elements
// into L and R subtree
int mid = start + (end - start) / 2;
// If element lies in L subtree
if (mid >= pos)
{
update(tree, 2 * index + 1, start,
mid, pos, val);
}
else
{
update(tree, 2 * index + 2, mid + 1,
end, pos, val);
}
// Update tree[index]
tree[index]
= tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to find the sum of array elements
// in the range [L, R]
static int FindSum(int[] tree, int start, int end,
int L, int R, int index)
{
// If start and end not lies in
// the range [L, R]
if (L > end || R < start)
{
return 0;
}
// If start and end comleately lies
// in the range [L, R]
if (L <= start && R >= end)
{
return tree[index];
}
int mid = start + (end - start) / 2;
// Stores sum from left subtree
int X = FindSum(tree, start, mid, L,
R, 2 * index + 1);
// Stores sum from right subtree
int Y = FindSum(tree, mid + 1, end, L,
R, 2 * index + 2);
return X + Y;
}
// Driver code
static void Main()
{
int[] arr = { 1, 2, 3, 4 };
int N = arr.Length;
int[] tree = new int[4 * N + 5];
build(tree, arr, 0, N - 1, 0);
int[,] Q = { { 2, 0, 3 }, { 1, 1, 5 }, { 2, 1, 2 } };
int cntQuey = 3;
for (int i = 0; i < cntQuey; i++)
{
if (Q[i, 0] == 1)
{
update(tree, 0, 0, N - 1,
Q[i, 1], Q[i, 2]);
}
else
{
if (Q[i, 1] % 2 == 0)
{
Console.Write(FindSum(tree, 0, N - 1,
Q[i, 1], Q[i, 2], 0) + " ");
}
else
{
Console.Write(-FindSum(tree, 0, N - 1,
Q[i, 1], Q[i, 2], 0) + " ");
}
}
}
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to build the segment tree
function build(tree, arr, start, end, index)
{
// If current node is a leaf node
// of the segment tree
if (start == end) {
if (start % 2 == 0) {
// Update tree[index]
tree[index] = arr[start];
}
else {
// Update tree[index]
tree[index] = -arr[start];
}
return;
}
// Divide the segment tree
var mid = start + parseInt((end - start) / 2);
// Update on L segment tree
build(tree, arr, start, mid,
2 * index + 1);
// Update on R segment tree
build(tree, arr, mid + 1, end,
2 * index + 2);
// Find the sum from L subtree
// and R subtree
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to update elements at index pos
// by val in the segment tree
function update(tree, index, start, end, pos, val)
{
// If current node is a leaf node
if (start == end) {
// If current index is even
if (start % 2 == 0) {
// Update tree[index]
tree[index] = val;
}
else {
// Update tree[index]
tree[index] = -val;
}
return;
}
// Divide the segment tree elements
// into L and R subtree
var mid = start + parseInt((end - start) / 2);
// If element lies in L subtree
if (mid >= pos) {
update(tree, 2 * index + 1, start,
mid, pos, val);
}
else {
update(tree, 2 * index + 2, mid + 1,
end, pos, val);
}
// Update tree[index]
tree[index]
= tree[2 * index + 1] + tree[2 * index + 2];
}
// Function to find the sum of array elements
// in the range [L, R]
function FindSum(tree, start, end, L, R, index)
{
// If start and end not lies in
// the range [L, R]
if (L > end || R < start) {
return 0;
}
// If start and end comleately lies
// in the range [L, R]
if (L <= start && R >= end) {
return tree[index];
}
var mid = start + parseInt((end - start) / 2);
// Stores sum from left subtree
var X = FindSum(tree, start, mid, L,
R, 2 * index + 1);
// Stores sum from right subtree
var Y = FindSum(tree, mid + 1, end, L,
R, 2 * index + 2);
return X + Y;
}
var arr = [1, 2, 3, 4 ];
var N = arr.length;
var tree = Array(4*N+5).fill(0);
build(tree, arr, 0, N - 1, 0);
var Q = [ [ 2, 0, 3 ], [ 1, 1, 5 ], [ 2, 1, 2 ] ];
var cntQuey = 3;
for (var i = 0; i < cntQuey; i++) {
if (Q[i][0] == 1) {
update(tree, 0, 0, N - 1,
Q[i][1], Q[i][2]);
}
else {
if (Q[i][1] % 2 == 0) {
document.write(FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0)
+ " ");
}
else {
document.write( -FindSum(tree, 0, N - 1,
Q[i][1], Q[i][2], 0)
+ " ");
}
}
}
</script>
Producción:
-2 2
Complejidad de tiempo: O(|Q| * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA