Un árbol de segmentos alternos OR/XOR Levelwise es un árbol de segmentos, de modo que en cada nivel se alternan las operaciones OR y XOR. En otras palabras, en el Nivel 1, los subárboles izquierdo y derecho se combinan mediante la operación OR, es decir, el Node principal = Hijo izquierdo O Hijo derecho y en el Nivel 2 el Node izquierdo
y los subárboles derecho se combinan mediante la operación XOR, es decir, Node principal = hijo izquierdo XOR hijo derecho
Este tipo de árbol de segmento tiene el siguiente tipo de estructura:
Las operaciones (OR) y (XOR) indican qué operación se llevó a cabo para fusionar el Node secundario
Dados 2 N Nodes de hoja, la tarea es construir dicho árbol de segmentos e imprimir el Node raíz
Ejemplos:
Input : Leaves = {1, 6, 3, 7, 5, 9, 10, 4}
Output : Value at Root Node = 3
Explanation : The image given above shows the
segment tree corresponding to the given
set leaf nodes.
Esta es una extensión del árbol de segmentos clásico donde representamos cada Node como un número entero y el Node principal se construye construyendo primero los subárboles izquierdo y derecho y luego combinando los resultados de los hijos izquierdo y derecho en el Node principal. Esta fusión de los elementos secundarios izquierdo y derecho en el Node principal se realiza mediante operaciones coherentes, por ejemplo, MIN()/MAX() en consultas mínimas de rango, suma, XOR, OR, AND, etc. Por operaciones coherentes queremos decir que esta operación se realiza para fusionar los elementos secundarios izquierdo y derecho de cualquier Node en el Node principal realizando la operación OP en sus resultados, donde OP es una operación consistente.
En este árbol de segmentos, llevamos dos operaciones que son: OR y XOR .
Ahora construimos el árbol de segmentos de manera similar a como lo hacemos en la versión clásica, pero ahora cuando pasemos recursivamente la información para los subárboles también pasaremos información sobre la operación a realizar en ese nivel ya que estas operaciones se alternan a nivel Es importante tener en cuenta que un Node padre cuando llama a sus hijos izquierdo y derecho, la misma información de operación se pasa a ambos hijos, ya que están en el mismo nivel.
representemos las dos operaciones, es decir, OR y XOR por 0 y 1 respectivamente. Entonces si en el Nivel i tenemos una operación OR en el Nivel (i + 1) tendremos una operación XOR. Allí, si el nivel i tiene 0 como operación, entonces el nivel (i + 1) tendrá 1 como operación
Operation at Level (i + 1) = ! (Operation at Level i)
where,
Operation at Level i ∈ {0, 1}
La relación padre-hijo para un Node de árbol de segmento se muestra en la siguiente imagen:
Ahora, debemos ver la operación que se llevará a cabo en el Node raíz.
Si observamos cuidadosamente la imagen, sería fácil darse cuenta de que si la altura del árbol es par, entonces el Node raíz es el resultado de la operación XOR de sus hijos izquierdo y derecho; de lo contrario, es el resultado de la operación OR.
C++
// C++ program to build levelwise OR/XOR alternating
// Segment tree
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index from
// corner indexes.
int getMid(int s, int e) { return s + (e - s) / 2; }
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// It's either 0 or 1.
void constructSTUtil(int arr[], int ss, int se, int* st,
int si, int operation)
{
// If there is one element in array, store it
// in current node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return;
}
// If there are more than one elements, then
// recur for left and right subtrees and store
// the sum of values in this node
int mid = getMid(ss, se);
// Build the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
constructSTUtil(arr, ss, mid, st, si * 2 + 1, !operation);
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2, !operation);
// merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation == 1) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
/* Function to construct segment tree from given array.
This function allocates memory for segment tree and
calls constructSTUtil() to fill the allocated memory */
int* constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int* st = new int[max_size];
// operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
int operationAtRoot = (x % 2 == 0 ? 0 : 1);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver Code
int main()
{
// leaf nodes
int leaves[] = { 1, 6, 3, 7, 5, 9, 10, 4 };
int n = sizeof(leaves) / sizeof(leaves[0]);
// Build the segment tree
int* segmentTree = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
int rootIndex = 0;
// print value at rootIndex
cout << "Value at Root Node = " << segmentTree[rootIndex];
}
Java
// Java program to build levelwise OR/XOR alternating
// Segment tree
class GFG{
// A utility function to get the middle index from
// corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// It's either 0 or 1.
static void constructSTUtil(int arr[], int ss, int se,
int st[], int si,
boolean operation)
{
// If there is one element in array, store it
// in current node of segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return;
}
// If there are more than one elements, then
// recur for left and right subtrees and store
// the sum of values in this node
int mid = getMid(ss, se);
// Build the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
constructSTUtil(arr, ss, mid, st,
si * 2 + 1, !operation);
constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2, !operation);
// Merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation)
{
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else
{
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
// Function to construct segment tree from
// given array. This function allocates
// memory for segment tree and calls
// constructSTUtil() to fill the allocated memory
static int[] constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(Math.ceil(Math.log(n) /
Math.log(2)));
// Maximum size of segment tree
int max_size = 2 * (int)Math.pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
boolean operationAtRoot = !(x % 2 == 0);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st,
0, operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver Code
public static void main(String[] args)
{
// Leaf nodes
int leaves[] = { 1, 6, 3, 7,
5, 9, 10, 4 };
int n = leaves.length;
// Build the segment tree
int[] segmentTree = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
int rootIndex = 0;
// Print value at rootIndex
System.out.println("Value at Root Node = " +
segmentTree[rootIndex]);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to build levelwise
# OR/XOR alternating Segment tree
import math
# A utility function to get the
# middle index from corner indexes.
def getMid(s, e):
return s + (e - s) // 2
# A recursive function that constructs
# Segment Tree for array[ss..se].
# 'si' is index of current node in segment
# tree 'st', operation denotes which operation
# is carried out at that level to merge the
# left and right child. It's either 0 or 1.
def constructSTUtil(arr, ss, se, st, si, operation):
# If there is one element in array,
# store it in current node of segment
# tree and return
if (ss == se) :
st[si] = arr[ss]
return
# If there are more than one elements,
# then recur for left and right subtrees
# and store the sum of values in this node
mid = getMid(ss, se)
# Build the left and the right subtrees by
# using the fact that operation at level
# (i + 1) = ! (operation at level i)
constructSTUtil(arr, ss, mid, st,
si * 2 + 1, not operation)
constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2, not operation)
# merge the left and right subtrees
# by checking the operation to be
# carried. If operation = 1, then
# do OR else XOR
if (operation == 1) :
# OR operation
st[si] = (st[2 * si + 1] |
st[2 * si + 2])
else :
# XOR operation
st[si] = (st[2 * si + 1] ^
st[2 * si + 2])
''' Function to construct segment tree
from given array. This function allocates
memory for segment tree and calls
constructSTUtil() to fill the allocated memory '''
def constructST(arr, n):
# Allocate memory for segment tree
# Height of segment tree
x = int(math.ceil(math.log2(n)))
# Maximum size of segment tree
max_size = 2 * int(pow(2, x)) - 1
# Allocate memory
st = [0] * max_size
# operation = 1(XOR) if Height of tree is
# even else it is 0(OR) for the root node
operationAtRoot = (0 if x % 2 == 0 else 1)
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1,
st, 0, operationAtRoot)
# Return the constructed segment tree
return st
# Driver Code
if __name__ == "__main__":
# leaf nodes
leaves = [ 1, 6, 3, 7, 5, 9, 10, 4 ]
n = len(leaves)
# Build the segment tree
segmentTree = constructST(leaves, n)
# Root node is at index 0 considering
# 0-based indexing in segment Tree
rootIndex = 0
# print value at rootIndex
print("Value at Root Node = " ,
segmentTree[rootIndex])
# This code is contributed by ChitraNayal
C#
// C# program to build levelwise OR/XOR
// alternating Segment tree
using System;
class GFG{
// A utility function to get the middle
// index from corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// It's either 0 or 1.
static void constructSTUtil(int[] arr, int ss, int se,
int[] st, int si,
bool operation)
{
// If there is one element in array, store it
// in current node of segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return;
}
// If there are more than one elements, then
// recur for left and right subtrees and store
// the sum of values in this node
int mid = getMid(ss, se);
// Build the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
constructSTUtil(arr, ss, mid, st,
si * 2 + 1, !operation);
constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2, !operation);
// Merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation)
{
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else
{
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
// Function to construct segment tree from
// given array. This function allocates
// memory for segment tree and calls
// constructSTUtil() to fill the allocated memory
static int[] constructST(int[] arr, int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(Math.Ceiling(Math.Log(n) /
Math.Log(2)));
// Maximum size of segment tree
int max_size = 2 * (int)Math.Pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
bool operationAtRoot = !(x % 2 == 0);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st,
0, operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver Code
static public void Main()
{
// Leaf nodes
int[] leaves = { 1, 6, 3, 7,
5, 9, 10, 4 };
int n = leaves.Length;
// Build the segment tree
int[] segmentTree = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
int rootIndex = 0;
// Print value at rootIndex
Console.WriteLine("Value at Root Node = " +
segmentTree[rootIndex]);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program to build levelwise OR/XOR
// alternating Segment tree
// A utility function to get the middle
// index from corner indexes.
function getMid(s, e) {
return s + Math.floor((e - s) / 2);
}
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// It's either 0 or 1.
function constructSTUtil(arr, ss, se, st, si, operation) {
// If there is one element in array, store it
// in current node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return;
}
// If there are more than one elements, then
// recur for left and right subtrees and store
// the sum of values in this node
let mid = getMid(ss, se);
// Build the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
constructSTUtil(arr, ss, mid, st, si * 2 + 1, !operation);
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2, !operation);
// Merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
// Function to construct segment tree from
// given array. This function allocates
// memory for segment tree and calls
// constructSTUtil() to fill the allocated memory
function constructST(arr, n) {
// Allocate memory for segment tree
// Height of segment tree
let x = Math.ceil(Math.log(n) / Math.log(2));
// Maximum size of segment tree
let max_size = 2 * Math.pow(2, x) - 1;
// Allocate memory
let st = new Array(max_size);
// Operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
let operationAtRoot = !(x % 2 == 0);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st,
0, operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver Code
// Leaf nodes
let leaves = [1, 6, 3, 7, 5, 9, 10, 4];
let n = leaves.length;
// Build the segment tree
let segmentTree = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
let rootIndex = 0;
// Print value at rootIndex
document.write("Value at Root Node = " + segmentTree[rootIndex]);
// This code is contributed by gfgking
</script>
Producción:
Value at Root Node = 3
La complejidad del tiempo para la construcción del árbol es O(n). Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
También podemos realizar actualizaciones de puntos de manera similar. Si obtenemos una actualización para actualizar la hoja en el índice i de las hojas de la array, entonces recorremos el árbol hasta el Node hoja y realizamos la actualización. Mientras volvemos al Node raíz, construimos el árbol nuevamente de manera similar a la función build() pasando la operación a realizar en cada nivel y almacenando el resultado de aplicar esa operación en los valores de sus hijos izquierdo y derecho y almacenando el resultado en ese Node.
Considere el siguiente árbol de segmentos después de realizar la actualización,
Leaves[0] = 13
Ahora el árbol de segmentos actualizado se ve así:
Aquí los Nodes en negro denotan el hecho de que fueron actualizados
C++
// C++ program to build levelwise OR/XOR alternating
// Segment tree (with updates)
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index from
// corner indexes.
int getMid(int s, int e) { return s + (e - s) / 2; }
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// Its either 0 or 1.
void constructSTUtil(int arr[], int ss, int se, int* st,
int si, int operation)
{
// If there is one element in array, store it in
// current node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return;
}
// If there are more than one elements, then recur
// for left and right subtrees and store the sum of
// values in this node
int mid = getMid(ss, se);
// Build the left and the right subtrees by using
// the fact that operation at level (i + 1) = !
// (operation at level i)
constructSTUtil(arr, ss, mid, st, si * 2 + 1, !operation);
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2, !operation);
// merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation == 1) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is
in input array.
val --> Value to be assigned to arr[i] */
void updateValueUtil(int* st, int ss, int se, int i,
int val, int si, int operation)
{
// Base Case: If the input index lies outside
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node,
// then update the value of the node and its
// children
// leaf node
if (ss == se && ss == i) {
st[si] = val;
return;
}
int mid = getMid(ss, se);
// Update the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
updateValueUtil(st, ss, mid, i, val, 2 * si + 1, !operation);
updateValueUtil(st, mid + 1, se, i, val, 2 * si + 2, !operation);
// merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation == 1) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
// The function to update a value in input array and
// segment tree. It uses updateValueUtil() to update the
// value in segment tree
void updateValue(int arr[], int* st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1) {
printf("Invalid Input");
return;
}
// Height of segment tree
int x = (int)(ceil(log2(n)));
// operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
int operationAtRoot = (x % 2 == 0 ? 0 : 1);
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, new_val, 0, operationAtRoot);
}
/* Function to construct segment tree from given array.
This function allocates memory for segment tree and
calls constructSTUtil() to fill the allocated memory */
int* constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int* st = new int[max_size];
// operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
int operationAtRoot = (x % 2 == 0 ? 0 : 1);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0, operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver Code
int main()
{
int leaves[] = { 1, 6, 3, 7, 5, 9, 10, 4 };
int n = sizeof(leaves) / sizeof(leaves[0]);
// Build the segment tree
int* segmentTree = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
int rootIndex = 0;
// print old value at rootIndex
cout << "Old Value at Root Node = "
<< segmentTree[rootIndex] << endl;
// perform update leaves[0] = 13
updateValue(leaves, segmentTree, n, 0, 13);
cout << "New Value at Root Node = "
<< segmentTree[rootIndex];
return 0;
}
Java
// Java program to build levelwise OR/XOR alternating
// Segment tree (with updates)
import java.io.*;
class GFG {
public static int log2(int N)
{
// calculate log2 N indirectly
// using log() method
int result = (int)(Math.log(N) / Math.log(2));
return result;
}
// A utility function to get the middle index from
// corner indexes.
public static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
// A recursive function that constructs Segment Tree
// for array[ss..se].
// si is index of current node in segment tree st
// operation denotes which operation is carried out
// at that level to merge the left and right child.
// Its either 0 or 1.
public static void constructSTUtil(int arr[], int ss,
int se, int st[],
int si,
int operation)
{
// If there is one element in array, store it in
// current node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return;
}
// If there are more than one elements, then recur
// for left and right subtrees and store the sum of
// values in this node
int mid = getMid(ss, se);
// Build the left and the right subtrees by using
// the fact that operation at level (i + 1) = !
// (operation at level i)
constructSTUtil(arr, ss, mid, st, si * 2 + 1,
operation ^ 1);
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2,
operation ^ 1);
// merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation == 1) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
/* A recursive function to update the nodes which have
the given index in their range. The following are
parameters st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This
index is in input array.
val --> Value to be assigned to arr[i] */
public static void updateValueUtil(int st[], int ss,
int se, int i,
int val, int si,
int operation)
{
// Base Case: If the input index lies outside
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node,
// then update the value of the node and its
// children
// leaf node
if (ss == se && ss == i) {
st[si] = val;
return;
}
int mid = getMid(ss, se);
// Update the left and the right subtrees by
// using the fact that operation at level
// (i + 1) = ! (operation at level i)
updateValueUtil(st, ss, mid, i, val, 2 * si + 1,
operation ^ 1);
updateValueUtil(st, mid + 1, se, i, val, 2 * si + 2,
operation ^ 1);
// merge the left and right subtrees by checking
// the operation to be carried. If operation = 1,
// then do OR else XOR
if (operation == 1) {
// OR operation
st[si] = (st[2 * si + 1] | st[2 * si + 2]);
}
else {
// XOR operation
st[si] = (st[2 * si + 1] ^ st[2 * si + 2]);
}
}
// The function to update a value in input array and
// segment tree. It uses updateValueUtil() to update the
// value in segment tree
public static void updateValue(int arr[], int st[],
int n, int i,
int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1) {
System.out.print("Invalid Input");
return;
}
// Height of segment tree
int x = (int)(Math.ceil(log2(n)));
// operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
int operationAtRoot = (x % 2 == 0 ? 0 : 1);
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, new_val, 0,
operationAtRoot);
}
/* Function to construct segment tree from given array.
This function allocates memory for segment tree and
calls constructSTUtil() to fill the allocated memory
*/
public static int[] constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(Math.ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)Math.pow(2, x) - 1;
// Allocate memory
int st[] = new int[max_size];
// operation = 1(XOR) if Height of tree is
// even else it is 0(OR) for the root node
int operationAtRoot = (x % 2 == 0 ? 0 : 1);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0,
operationAtRoot);
// Return the constructed segment tree
return st;
}
// Driver code
public static void main(String[] args)
{
int leaves[] = { 1, 6, 3, 7, 5, 9, 10, 4 };
int n = leaves.length;
// Build the segment tree
int segmentTree[] = constructST(leaves, n);
// Root node is at index 0 considering
// 0-based indexing in segment Tree
int rootIndex = 0;
// print old value at rootIndex
System.out.println("Old Value at Root Node = "
+ segmentTree[rootIndex]);
// perform update leaves[0] = 13
updateValue(leaves, segmentTree, n, 0, 13);
System.out.print("New Value at Root Node = "
+ segmentTree[rootIndex]);
}
}
// This code is contributed by Rohit Pradhan
Producción:
Old Value at Root Node = 3 New Value at Root Node = 11
La complejidad del tiempo de actualización también es O (Iniciar sesión). Para actualizar un valor de hoja, procesamos un Node en cada nivel y el número de niveles es O (Iniciar sesión).