Dada una array de tamaño N. Puede haber múltiples consultas de los siguientes tipos.
- actualizar (l, r) : en la actualización, voltea (multiplica a[i] por -1) el valor de a[i] donde l <= i <= r . En términos simples, cambie el signo de a[i] para el rango dado.
- consulta (l, r) : en la consulta, imprime la suma de la array en el rango dado que incluye tanto l como r.
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 4, 5 }
actualizar (0, 2)
consulta (0, 4)
Salida: 3
Después de aplicar la operación de actualización, la array se convierte en { -1, -2, -3, 4, 5 } .
Entonces la suma es 3
Entrada: arr[] = { 1, 2, 3, 4, 5 }
actualizar (0, 4)
consulta (0, 4)
Salida: -15
Después de aplicar la operación de actualización, la array se convierte en { -1, -2 , -3, -4, -5 } .
Entonces la suma es -15
requisitos previos:
Enfoque:
cree un árbol de segmentos donde cada Node almacene la suma de su hijo izquierdo y derecho hasta que sea un Node de hoja donde se almacena la array.
Para la operación de actualización :
cree un árbol llamado perezoso del mismo tamaño que el árbol de segmento anterior donde el árbol almacena la suma de sus tiendas secundarias y perezosas, ya sea que se les haya pedido que se inviertan o no. Si lazy se establece en 1 para un rango, entonces todos los valores debajo de ese rango deben invertirse. Para la actualización se utilizan las siguientes operaciones:
- Si el árbol de segmento actual tiene un valor perezoso de 1, actualice el Node del árbol de segmento actual cambiando el signo, ya que el valor debe invertirse y también cambiar el valor de perezoso de su hijo y restablecer su propio perezoso a 0.
- Si el rango del Node actual se encuentra completamente en el rango de consulta de actualización, actualice el Node actual cambiando su signo y también cambie el valor de perezoso de su hijo si no es un Node de hoja.
- Si el rango del Node actual se superpone con el rango de actualización, realice la recursión para sus hijos y actualice el Node actual usando la suma de sus hijos.
Para la operación de consulta :
si lazy se establece en 1, cambie el signo del Node actual y restablezca el Node actual lazy a 0 y también cambie el valor de lazy de su hijo si no es un Node hoja. Y luego haga una consulta simple como se hizo en el árbol de segmentos.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 15
int tree[MAX] = { 0 };
int lazy[MAX] = { 0 };
// Function to build the segment tree
void build(int arr[],int node, int a, int b)
{
if (a == b) {
tree[node] = arr[a];
return;
}
// left child
build(arr,2 * node, a, (a + b) / 2);
// right child
build(arr,2 * node + 1, 1 + (a + b) / 2, b);
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
void update_tree(int node, int a,
int b, int i, int j)
{
// If lazy of node is 1 then
// value in current node
// needs to be flipped
if (lazy[node] != 0) {
// Update it
tree[node] = tree[node] * (-1);
if (a != b) {
// flip value in lazy
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
// Reset the node lazy value
lazy[node] = 0;
}
// Current segment is not
// within range [i, j]
if (a > b || a > j || b < i)
return;
// Segment is fully
// within range
if (a >= i && b <= j) {
tree[node] = tree[node] * (-1);
// Not leaf node
if (a != b) {
// Flip the value as if lazy is
// 1 and again asked to flip
// value then without flipping
// value two times
lazy[node * 2] =
!(lazy[node * 2]);
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
return;
}
// Updating left child
update_tree(node * 2, a,
(a + b) / 2, i, j);
// Updating right child
update_tree(1 + node * 2, 1 +
(a + b) / 2, b, i, j);
// Updating root with
// sum of its child
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
int query_tree(int node, int a,
int b, int i, int j)
{
// Out of range
if (a > b || a > j || b < i)
return 0;
// If lazy of node is 1 then value
// in current node needs to be flipped
if (lazy[node] != 0) {
tree[node] = tree[node] * (-1);
if (a != b) {
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
lazy[node] = 0;
}
// Current segment is totally
// within range [i, j]
if (a >= i && b <= j)
return tree[node];
// Query left child
int q1 = query_tree(node * 2, a,
(a + b) / 2, i, j);
// Query right child
int q2 = query_tree(1 + node * 2,
1 + (a + b) / 2, b, i, j);
// Return final result
return q1 + q2;
}
int main()
{
int arr[]={1,2,3,4,5};
int n=sizeof(arr)/sizeof(arr[0]);
// Building segment tree
build(arr,1, 0, n - 1);
// Array is { 1, 2, 3, 4, 5 }
cout << query_tree(1, 0, n - 1, 0, 4) << endl;
// Flip range 0 to 4
update_tree(1, 0, n - 1, 0, 4);
// Array becomes { -1, -2, -3, -4, -5 }
cout << query_tree(1, 0, n - 1, 0, 4) << endl;
// Flip range 0 t0 2
update_tree(1, 0, n - 1, 0, 2);
// Array becomes { 1, 2, 3, -4, -5 }
cout << query_tree(1, 0, n - 1, 0, 4) << endl;
}
Java
// Java implementation of the approach
class GFG
{
static final int MAX = 15;
static int tree[] = new int[MAX];
static boolean lazy[] = new boolean[MAX];
// Function to build the segment tree
static void build(int arr[],int node, int a, int b)
{
if (a == b)
{
tree[node] = arr[a];
return;
}
// left child
build(arr,2 * node, a, (a + b) / 2);
// right child
build(arr,2 * node + 1, 1 + (a + b) / 2, b);
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
static void update_tree(int node, int a,
int b, int i, int j)
{
// If lazy of node is 1 then
// value in current node
// needs to be flipped
if (lazy[node] != false)
{
// Update it
tree[node] = tree[node] * (-1);
if (a != b)
{
// flip value in lazy
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
// Reset the node lazy value
lazy[node] = false;
}
// Current segment is not
// within range [i, j]
if (a > b || a > j || b < i)
return;
// Segment is fully
// within range
if (a >= i && b <= j)
{
tree[node] = tree[node] * (-1);
// Not leaf node
if (a != b)
{
// Flip the value as if lazy is
// 1 and again asked to flip
// value then without flipping
// value two times
lazy[node * 2] =
!(lazy[node * 2]);
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
return;
}
// Updating left child
update_tree(node * 2, a,
(a + b) / 2, i, j);
// Updating right child
update_tree(1 + node * 2, 1 +
(a + b) / 2, b, i, j);
// Updating root with
// sum of its child
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
static int query_tree(int node, int a,
int b, int i, int j)
{
// Out of range
if (a > b || a > j || b < i)
return 0;
// If lazy of node is 1 then value
// in current node needs to be flipped
if (lazy[node] != false)
{
tree[node] = tree[node] * (-1);
if (a != b)
{
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
lazy[node] = false;
}
// Current segment is totally
// within range [i, j]
if (a >= i && b <= j)
return tree[node];
// Query left child
int q1 = query_tree(node * 2, a,
(a + b) / 2, i, j);
// Query right child
int q2 = query_tree(1 + node * 2,
1 + (a + b) / 2, b, i, j);
// Return final result
return q1 + q2;
}
// Driver code
public static void main(String[] args)
{
int arr[]={1, 2, 3, 4, 5};
int n=arr.length;
// Building segment tree
build(arr,1, 0, n - 1);
// Array is { 1, 2, 3, 4, 5 }
System.out.print(query_tree(1, 0, n - 1, 0, 4) +"\n");
// Flip range 0 to 4
update_tree(1, 0, n - 1, 0, 4);
// Array becomes { -1, -2, -3, -4, -5 }
System.out.print(query_tree(1, 0, n - 1, 0, 4) +"\n");
// Flip range 0 t0 2
update_tree(1, 0, n - 1, 0, 2);
// Array becomes { 1, 2, 3, -4, -5 }
System.out.print(query_tree(1, 0, n - 1, 0, 4) +"\n");
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
MAX = 15
tree = [0]*MAX
lazy = [0]*MAX
# Function to build the segment tree
def build(arr,node, a, b):
if (a == b):
tree[node] = arr[a]
return
# left child
build(arr,2 * node, a, (a + b) // 2)
# right child
build(arr,2 * node + 1, 1 + (a + b) // 2, b)
tree[node] = tree[node * 2] +tree[node * 2 + 1]
def update_tree(node, a,b, i, j):
# If lazy of node is 1 then
# value in current node
# needs to be flipped
if (lazy[node] != 0):
# Update it
tree[node] = tree[node] * (-1)
if (a != b):
# flip value in lazy
lazy[node * 2] =not (lazy[node * 2])
# flip value in lazy
lazy[node * 2 + 1] =not (lazy[node * 2 + 1])
# Reset the node lazy value
lazy[node] = 0
# Current segment is not
# within range [i, j]
if (a > b or a > j or b < i):
return
# Segment is fully
# within range
if (a >= i and b <= j):
tree[node] = tree[node] * (-1)
# Not leaf node
if (a != b):
# Flip the value as if lazy is
# 1 and again asked to flip
# value then without flipping
# value two times
lazy[node * 2] = not (lazy[node * 2])
lazy[node * 2 + 1] = not (lazy[node * 2 + 1])
return
# Updating left child
update_tree(node * 2, a,(a + b) // 2, i, j)
# Updating right child
update_tree(1 + node * 2, 1 +(a + b) // 2, b, i, j)
# Updating root with
# sum of its child
tree[node] = tree[node * 2] +tree[node * 2 + 1]
def query_tree(node, a,b, i, j):
# Out of range
if (a > b or a > j or b < i):
return 0
# If lazy of node is 1 then value
# in current node needs to be flipped
if (lazy[node] != 0):
tree[node] = tree[node] * (-1)
if (a != b):
lazy[node * 2] =not (lazy[node * 2])
# flip value in lazy
lazy[node * 2 + 1] = not (lazy[node * 2 + 1])
lazy[node] = 0
# Current segment is totally
# within range [i, j]
if (a >= i and b <= j):
return tree[node]
# Query left child
q1 = query_tree(node * 2, a,(a + b) // 2, i, j)
# Query right child
q2 = query_tree(1 + node * 2,1 + (a + b) // 2, b, i, j)
# Return final result
return q1 + q2
# Driver code
if __name__ == '__main__':
arr=[1,2,3,4,5]
n=len(arr)
# Building segment tree
build(arr,1, 0, n - 1)
# Array is { 1, 2, 3, 4, 5
print(query_tree(1, 0, n - 1, 0, 4))
# Flip range 0 to 4
update_tree(1, 0, n - 1, 0, 4)
# Array becomes { -1, -2, -3, -4, -5
print(query_tree(1, 0, n - 1, 0, 4))
# Flip range 0 t0 2
update_tree(1, 0, n - 1, 0, 2)
# Array becomes { 1, 2, 3, -4, -5
print(query_tree(1, 0, n - 1, 0, 4))
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static readonly int MAX = 15;
static int []tree = new int[MAX];
static bool []lazy = new bool[MAX];
// Function to build the segment tree
static void build(int []arr,int node, int a, int b)
{
if (a == b)
{
tree[node] = arr[a];
return;
}
// left child
build(arr, 2 * node, a, (a + b) / 2);
// right child
build(arr, 2 * node + 1, 1 + (a + b) / 2, b);
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
static void update_tree(int node, int a,
int b, int i, int j)
{
// If lazy of node is 1 then
// value in current node
// needs to be flipped
if (lazy[node] != false)
{
// Update it
tree[node] = tree[node] * (-1);
if (a != b)
{
// flip value in lazy
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
// Reset the node lazy value
lazy[node] = false;
}
// Current segment is not
// within range [i, j]
if (a > b || a > j || b < i)
return;
// Segment is fully
// within range
if (a >= i && b <= j)
{
tree[node] = tree[node] * (-1);
// Not leaf node
if (a != b)
{
// Flip the value as if lazy is
// 1 and again asked to flip
// value then without flipping
// value two times
lazy[node * 2] =
!(lazy[node * 2]);
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
return;
}
// Updating left child
update_tree(node * 2, a,
(a + b) / 2, i, j);
// Updating right child
update_tree(1 + node * 2, 1 +
(a + b) / 2, b, i, j);
// Updating root with
// sum of its child
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
static int query_tree(int node, int a,
int b, int i, int j)
{
// Out of range
if (a > b || a > j || b < i)
return 0;
// If lazy of node is 1 then value
// in current node needs to be flipped
if (lazy[node] != false)
{
tree[node] = tree[node] * (-1);
if (a != b)
{
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
lazy[node] = false;
}
// Current segment is totally
// within range [i, j]
if (a >= i && b <= j)
return tree[node];
// Query left child
int q1 = query_tree(node * 2, a,
(a + b) / 2, i, j);
// Query right child
int q2 = query_tree(1 + node * 2,
1 + (a + b) / 2, b, i, j);
// Return readonly result
return q1 + q2;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5};
int n = arr.Length;
// Building segment tree
build(arr, 1, 0, n - 1);
// Array is { 1, 2, 3, 4, 5 }
Console.Write(query_tree(1, 0, n - 1, 0, 4) +"\n");
// Flip range 0 to 4
update_tree(1, 0, n - 1, 0, 4);
// Array becomes { -1, -2, -3, -4, -5 }
Console.Write(query_tree(1, 0, n - 1, 0, 4) +"\n");
// Flip range 0 t0 2
update_tree(1, 0, n - 1, 0, 2);
// Array becomes { 1, 2, 3, -4, -5 }
Console.Write(query_tree(1, 0, n - 1, 0, 4) +"\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
let MAX = 15;
let tree = new Array(MAX).fill(0);
let lazy = new Array(MAX).fill(0);
// Function to build the segment tree
function build(arr,node, a, b)
{
if (a == b) {
tree[node] = arr[a];
return;
}
// left child
build(arr,2 * node, a, Math.floor((a + b) / 2));
// right child
build(arr,2 * node + 1, 1 + Math.floor((a + b) / 2), b);
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
function update_tree(node, a, b, i, j)
{
// If lazy of node is 1 then
// value in current node
// needs to be flipped
if (lazy[node] != 0) {
// Update it
tree[node] = tree[node] * (-1);
if (a != b) {
// flip value in lazy
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
// Reset the node lazy value
lazy[node] = 0;
}
// Current segment is not
// within range [i, j]
if (a > b || a > j || b < i)
return;
// Segment is fully
// within range
if (a >= i && b <= j) {
tree[node] = tree[node] * (-1);
// Not leaf node
if (a != b) {
// Flip the value as if lazy is
// 1 and again asked to flip
// value then without flipping
// value two times
lazy[node * 2] =
!(lazy[node * 2]);
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
return;
}
// Updating left child
update_tree(node * 2, a,
Math.floor((a + b) / 2), i, j);
// Updating right child
update_tree(1 + node * 2, 1 +
Math.floor((a + b) / 2), b, i, j);
// Updating root with
// sum of its child
tree[node] = tree[node * 2] +
tree[node * 2 + 1];
}
function query_tree(node, a, b, i, j)
{
// Out of range
if (a > b || a > j || b < i)
return 0;
// If lazy of node is 1 then value
// in current node needs to be flipped
if (lazy[node] != 0) {
tree[node] = tree[node] * (-1);
if (a != b) {
lazy[node * 2] =
!(lazy[node * 2]);
// flip value in lazy
lazy[node * 2 + 1] =
!(lazy[node * 2 + 1]);
}
lazy[node] = 0;
}
// Current segment is totally
// within range [i, j]
if (a >= i && b <= j)
return tree[node];
// Query left child
let q1 = query_tree(node * 2, a,
Math.floor((a + b) / 2), i, j);
// Query right child
let q2 = query_tree(1 + node * 2,
1 + Math.floor((a + b) / 2), b, i, j);
// Return final result
return q1 + q2;
}
let arr = [ 1,2,3,4,5];
let n = arr.length;
// Building segment tree
build(arr,1, 0, n - 1);
// Array is { 1, 2, 3, 4, 5 }
document.write(query_tree(1, 0, n - 1, 0, 4) + "<br>");
// Flip range 0 to 4
update_tree(1, 0, n - 1, 0, 4);
// Array becomes { -1, -2, -3, -4, -5 }
document.write(query_tree(1, 0, n - 1, 0, 4) + "<br>");
// Flip range 0 t0 2
update_tree(1, 0, n - 1, 0, 2);
// Array becomes { 1, 2, 3, -4, -5 }
document.write(query_tree(1, 0, n - 1, 0, 4) + "<br>");
// This code is contributed by gfgking
</script>
Producción:
15 -15 -3
Complejidad del tiempo: O(log(N))
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por gyanendra371 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA