Elemento sobrante después de realizar operaciones alternas Bitwise OR y Bitwise XOR en pares adyacentes

Dada una array de N (siempre una potencia de 2) elementos y Q consultas.
Cada consulta consta de dos elementos, un índice y un valor … Necesitamos escribir un programa que asigne un valor a un índice e imprima el único elemento que queda después de realizar las siguientes operaciones para cada consulta:

  • En pasos alternativos, realice operaciones OR bit a bit y operaciones XOR bit a bit en los elementos adyacentes.
  • En la primera iteración, seleccione, seleccione n/2 pares moviéndose de izquierda a derecha y haga un OR bit a bit de todos los valores de par. En la segunda iteración, seleccione (n/2)/2 pares sobrantes y haga un XOR bit a bit en ellos. En la tercera iteración, seleccione, seleccione ((n/2)/2)/2 pares sobrantes moviéndose de izquierda a derecha, y haga un OR bit a bit de todos los valores de par.
  • Continúe con los pasos anteriores hasta que nos quede un solo elemento.

Ejemplos:

Input : n = 4   m = 2 
        arr = [1, 4, 5, 6] 
        Queries- 
        1st: index=0 value=2  
        2nd: index=3 value=5
Output : 1 
         3 
Explanation: 

1st query:
Assigning 2 to index 0, the sequence is now 
[2, 4, 5, 6]. 
1st iteration: There are 4/2=2 pairs (2, 4) and (5, 6) 
2 OR 4 gives 6, and 5 OR 6 gives us 7. So the 
sequence is now [6, 7]. 

2nd iteration: There is 1 pair left now (6, 7) 
6^7=1. 

Hence the last element left is 1 which is the 
answer to our first query. 

2nd Query:
Assigning 5 to index 3, the sequence is now 
[2, 4, 5, 5]. 
1st iteration: There are 4/2=2 pairs (2, 4) and (5, 5) 
2 OR 4 gives 6, and 5 OR 5 gives us 5. So the 
sequence is now [6, 5]. 

2nd iteration: There is 1 pair left now (6, 5) 
6^5=3. 

Hence the last element left is 3 which is the
answer to our second query. 

Enfoque ingenuo : el enfoque ingenuo es realizar cada paso hasta que nos quede un elemento. Usando un vector 2-D, almacenaremos los elementos resultantes que quedan después de cada paso. V[pasos-1][0..tamaño] da el número de elementos en el paso anterior. Si el número de paso es impar, realizamos una operación OR bit a bit, de lo contrario, se realiza una operación XOR bit a bit. Repita los pasos hasta que tengamos un sobrante con un elemento. El último elemento que queda será nuestra respuesta. 

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

C++

// CPP program to print the Leftover element after
// performing alternate Bitwise OR and Bitwise XOR
// operations to the pairs.
#include <bits/stdc++.h>
using namespace std;
#define N 1000
  
int lastElement(int a[],int n)
{
    // count the step number
    int steps = 1;
    vector<int>v[N];
  
    // if one element is there, it will be the answer
    if (n==1) return a[0];
  
  
    // at first step we do a bitwise OR
    for (int i = 0 ; i < n ; i += 2)
        v[steps].push_back(a[i] | a[i+1]);
  
  
    // keep on doing bitwise operations till the
    // last element is left
    while (v[steps].size()>1)
    {
  
        steps += 1;
  
        // perform operations
        for (int i = 0 ; i < v[steps-1].size(); i+=2)
        {
            // if step is the odd step
            if (steps&1)
                v[steps].push_back(v[steps-1][i] | v[steps-1][i+1]);
            else  // even step
                v[steps].push_back(v[steps-1][i] ^ v[steps-1][i+1]);
        }
    }
  
    // answer when one element is left
    return v[steps][0];
}
  
// Driver Code
int main()
{
    int a[] = {1, 4, 5, 6};
    int n = sizeof(a)/sizeof(a[0]);
  
    // 1st query
    int index = 0;
    int value = 2;
    a[0] = 2;
    cout << lastElement(a,n) << endl;
  
    // 2nd query
    index = 3;
    value = 5;
    a[index] = value;
    cout << lastElement(a,n)  << endl;
  
    return 0;
}

Java

// Java program to print the Leftover element 
// after performing alternate Bitwise OR and 
// Bitwise XOR operations to the pairs.
import java.util.*;
  
class GFG
{
static int N = 1000;
  
static int lastElement(int a[], int n)
{
    // count the step number
    int steps = 1;
    Vector<Integer> []v = new Vector[N];
    for (int i = 0; i < N; i++)
        v[i] = new Vector<Integer>();
  
    // if one element is there, 
    // it will be the answer
    if (n == 1) return a[0];
  
    // at first step we do a bitwise OR
    for (int i = 0 ; i < n ; i += 2)
        v[steps].add(a[i] | a[i + 1]);
  
    // keep on doing bitwise operations 
    // till the last element is left
    while (v[steps].size() > 1)
    {
  
        steps += 1;
  
        // perform operations
        for (int i = 0; i < v[steps - 1].size(); i += 2)
        {
            // if step is the odd step
            if (steps % 2 == 1)
                v[steps].add(v[steps - 1].get(i) | 
                             v[steps - 1].get(i + 1));
            else // even step
                v[steps].add(v[steps - 1].get(i) ^ 
                             v[steps - 1].get(i + 1));
        }
    }
  
    // answer when one element is left
    return v[steps].get(0);
}
  
// Driver Code
public static void main(String[] args)
{
    int a[] = {1, 4, 5, 6};
    int n = a.length;
  
    // 1st query
    int index = 0;
    int value = 2;
    a[0] = 2;
    System.out.println(lastElement(a, n));
  
    // 2nd query
    index = 3;
    value = 5;
    a[index] = value;
    System.out.println(lastElement(a, n));
}
}
  
// This code is contributed by 29AjayKumar

Python3

# Python3 program to print the Leftover element 
# after performing alternate Bitwise OR and 
# Bitwise XOR operations to the pairs. 
N = 1000 
  
def lastElement(a, n): 
   
    # count the step number 
    steps = 1 
    v = [[] for i in range(n)] 
  
    # if one element is there, it will be the answer 
    if n == 1: return a[0] 
  
    # at first step we do a bitwise OR 
    for i in range(0, n, 2): 
        v[steps].append(a[i] | a[i+1]) 
  
    # keep on doing bitwise operations 
    # till the last element is left 
    while len(v[steps]) > 1: 
      
        steps += 1 
        # perform operations 
        for i in range(0, len(v[steps-1]), 2): 
           
            # if step is the odd step 
            if steps & 1: 
                v[steps].append(v[steps-1][i] | v[steps-1][i+1]) 
            else: # even step 
                v[steps].append(v[steps-1][i] ^ v[steps-1][i+1]) 
           
    # answer when one element is left 
    return v[steps][0] 
  
# Driver Code 
if __name__ == "__main__": 
   
    a = [1, 4, 5, 6]
    n = len(a) 
  
    # 1st query 
    index, value, a[0] = 0, 2, 2 
    print(lastElement(a,n))
  
    # 2nd query 
    index, value = 3, 5 
    value = 5 
    a[index] = value 
    print(lastElement(a,n))
   
# This code is contributed by Rituraj Jain

C#

// C# program to print the Leftover element 
// after performing alternate Bitwise OR and 
// Bitwise XOR operations to the pairs.
using System;
using System.Collections.Generic;
  
class GFG
{
static int N = 1000;
  
static int lastElement(int []a, int n)
{
    // count the step number
    int steps = 1;
    List<int> []v = new List<int>[N];
    for (int i = 0; i < N; i++)
        v[i] = new List<int>();
  
    // if one element is there, 
    // it will be the answer
    if (n == 1) 
        return a[0];
  
    // at first step we do a bitwise OR
    for (int i = 0 ; i < n ; i += 2)
        v[steps].Add(a[i] | a[i + 1]);
  
    // keep on doing bitwise operations 
    // till the last element is left
    while (v[steps].Count > 1)
    {
        steps += 1;
  
        // perform operations
        for (int i = 0; i < v[steps - 1].Count; i += 2)
        {
            // if step is the odd step
            if (steps % 2 == 1)
                v[steps].Add(v[steps - 1][i] | 
                             v[steps - 1][i + 1]);
            else // even step
                v[steps].Add(v[steps - 1][i] ^ 
                             v[steps - 1][i + 1]);
        }
    }
  
    // answer when one element is left
    return v[steps][0];
}
  
// Driver Code
public static void Main(String[] args)
{
    int []a = {1, 4, 5, 6};
    int n = a.Length;
  
    // 1st query
    int index = 0;
    int value = 2;
    a[0] = 2;
    Console.WriteLine(lastElement(a, n));
  
    // 2nd query
    index = 3;
    value = 5;
    a[index] = value;
    Console.WriteLine(lastElement(a, n));
}
}
  
// This code is contributed by 29AjayKumar

Javascript

<script>
  
// Javascript program to print the Leftover element after
// performing alternate Bitwise OR and Bitwise XOR
// operations to the pairs.
var N = 1000
  
function lastElement(a,n)
{
    // count the step number
    var steps = 1;
    var v = Array.from(Array(N), ()=>Array(0));
  
    // if one element is there, it will be the answer
    if (n==1) 
        return a[0];
  
  
    // at first step we do a bitwise OR
    for (var i = 0 ; i < n ; i += 2)
        v[steps].push(a[i] | a[i+1]);
  
  
    // keep on doing bitwise operations till the
    // last element is left
    while (v[steps].length>1)
    {
  
        steps += 1;
  
        // perform operations
        for (var i = 0 ; i < v[steps-1].length; i+=2)
        {
            // if step is the odd step
            if (steps&1)
                v[steps].push(v[steps-1][i] | v[steps-1][i+1]);
            else  // even step
                v[steps].push(v[steps-1][i] ^ v[steps-1][i+1]);
        }
    }
  
    // answer when one element is left
    return v[steps][0];
}
  
// Driver Code
var a = [1, 4, 5, 6];
var n = a.length;
// 1st query
var index = 0;
var value = 2;
a[0] = 2;
document.write( lastElement(a,n) + "<br>");
// 2nd query
index = 3;
value = 5;
a[index] = value;
document.write( lastElement(a,n));
  
</script>

Producción: 

1
3

Complejidad de tiempo: O(N * 2 N
 Complejidad de espacio : O(N ^ 2)

Enfoque eficiente : El enfoque eficiente es utilizar un árbol de segmentos . A continuación se muestra el enfoque de árbol de segmentos completo utilizado para resolver el problema. 

Construyendo el árbol
Las hojas del árbol de segmentos almacenarán la array de valores y sus padres almacenarán el OR de las hojas. Moviéndose hacia arriba en el árbol, con cada paso alternativo, el padre almacena XOR bit a bit o OR bit a bit entre el hijo izquierdo y derecho. En cada iteración impar, realizamos el OR bit a bit de los pares y , de manera similar, realizamos el XOR bit a bit de los pares en cada operación par . Entonces, el padre impar almacenará el OR bit a bit del hijo izquierdo y derecho. De manera similar, el padre con número par almacena el XOR bit a bit del hijo izquierdo y derecho. level[] es una array que almacena niveles de cada padre a partir de 1, para determinar si el par (hijo derecho e hijo izquierdo) debajo de él realiza una operación OR o una operación XOR.La raíz del árbol será nuestra respuesta a la secuencia dada después de cada operación de actualización. 

Leftover element after performing alternate Bitwise OR and Bitwise XOR operations on adjacent pairs

.La imagen de arriba explica la construcción del árbol. Si la secuencia fue [1, 2, 3, 4, 5, 6, 7, 8], luego de 3 iteraciones, nos quedará 12, que es nuestra respuesta y se almacena en la raíz. 

Consulta
de respuesta No es necesario reconstruir el árbol completo para realizar una operación de actualización. Para hacer una actualización, debemos encontrar una ruta desde la raíz hasta la hoja correspondiente y recalcular los valores solo para los padres que se encuentran en la ruta encontrada. 
Nivel de padre: 
usando DP en árboles , podemos almacenar fácilmente el nivel de cada padre. Inicialice el nivel de los Nodes hoja en 0 y siga agregando a medida que avanzamos hacia cada padre. 
La relación de recurrencia para calcular el nivel de padre es:  

nivel[padre] = nivel[hijo] + 1 
Aquí, un hijo es 2*pos + 1 o 2*pos + 2

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

C++

// CPP program to print the Leftover element after
// performing alternate Bitwise OR and
// Bitwise XOR operations to the pairs.
#include <bits/stdc++.h>
using namespace std;
#define N 1000
  
// array to store the tree
int tree[N];
  
// array to store the level of every parent
int level[N];
  
// function to construct the tree
void constructTree(int low, int high, int pos, int a[])
{
    if (low == high)
    {
        // level of child is always 0
        level[pos] = 0;
        tree[pos] = a[high];
        return;
    }
    int mid = (low + high) / 2;
  
    // recursive call
    constructTree(low, mid, 2 * pos + 1, a);
    constructTree(mid + 1, high, 2 * pos + 2, a);
  
    // increase the level of every parent, which is
    // level of child + 1
    level[pos] = level[2 * pos + 1] + 1;
  
    // if the parent is at odd level, then do a
    // bitwise OR
    if (level[pos] & 1)
        tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2];
  
    // if the parent is at even level, then
    // do a bitwise XOR
    else
        tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2];
}
  
// function that updates the tree
void update(int low, int high, int pos, int index, int a[])
{
    // if it is a leaf and the leaf which is 
    // to be updated
    if (low == high and low == index)
    {
        tree[pos] = a[low];
        return;
    }
  
    // out of range
    if (index < low || index > high)
        return;
  
    // not a leaf then recurse
    if (low != high)
    {
        int mid = (low + high) / 2;
  
        // recursive call
        update(low, mid, 2 * pos + 1, index, a);
        update(mid + 1, high, 2 * pos + 2, index, a);
  
        // check if the parent is at odd or even level
        // and perform OR or XOR according to that
        if (level[pos] & 1)
            tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2];
        else
            tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2];
    }
}
  
// function that assigns value to a[index]
// and calls update function to update the tree
void updateValue(int index, int value, int a[], int n)
{
    a[index] = value;
    update(0, n - 1, 0, index, a);
}
  
// Driver Code
int main()
{
    int a[] = { 1, 4, 5, 6 };
    int n = sizeof(a) / sizeof(a[0]);
  
    // builds the tree
    constructTree(0, n - 1, 0, a);
  
    // 1st query
    int index = 0;
    int value = 2;
    updateValue(index, value, a, n);
    cout << tree[0] << endl;
  
    // 2nd query
    index = 3;
    value = 5;
    updateValue(index, value, a, n);
    cout << tree[0] << endl;
  
    return 0;
}

Java

// java program to print the Leftover
// element after performing alternate
// Bitwise OR and Bitwise XOR operations
// to the pairs.
import java .io.*;
  
public class GFG {
  
    static int N = 1000;
      
    // array to store the tree
    static int []tree = new int[N];
      
    // array to store the level of
    // every parent
    static int []level = new int[N];
      
    // function to construct the tree
    static void constructTree(int low, int high,
                               int pos, int []a)
    {
        if (low == high)
        {
              
            // level of child is
            // always 0
            level[pos] = 0;
            tree[pos] = a[high];
            return;
        }
        int mid = (low + high) / 2;
      
        // recursive call
        constructTree(low, mid, 2 * pos + 1, a);
          
        constructTree(mid + 1, high, 
                                2 * pos + 2, a);
      
        // increase the level of every parent,
        // which is level of child + 1
        level[pos] = level[2 * pos + 1] + 1;
      
        // if the parent is at odd level, then
        // do a bitwise OR
        if ((level[pos] & 1) > 0)
            tree[pos] = tree[2 * pos + 1] |
                              tree[2 * pos + 2];
      
        // if the parent is at even level, then
        // do a bitwise XOR
        else
            tree[pos] = tree[2 * pos + 1] ^ 
                              tree[2 * pos + 2];
    }
      
    // function that updates the tree
    static void update(int low, int high, int pos,
                               int index, int []a)
    {
          
        // if it is a leaf and the leaf which is 
        // to be updated
        if (low == high && low == index)
        {
            tree[pos] = a[low];
            return;
        }
      
        // out of range
        if (index < low || index > high)
            return;
      
        // not a leaf then recurse
        if (low != high)
        {
            int mid = (low + high) / 2;
      
            // recursive call
            update(low, mid, 2 * pos + 1, index, a);
              
            update(mid + 1, high, 2 * pos + 2,
                                          index, a);
      
            // check if the parent is at odd or
            // even level and perform OR or XOR
            // according to that
            if ((level[pos] & 1) > 0)
                tree[pos] = tree[2 * pos + 1] |
                                  tree[2 * pos + 2];
            else
                tree[pos] = tree[2 * pos + 1] ^
                                  tree[2 * pos + 2];
        }
    }
      
    // function that assigns value to a[index]
    // and calls update function to update the
    // tree
    static void updateValue(int index, int value,
                                   int []a, int n)
    {
        a[index] = value;
        update(0, n - 1, 0, index, a);
    }
      
    // Driver Code
    static public void main (String[] args)
    {
        int []a = { 1, 4, 5, 6 };
        int n = a.length;;
      
        // builds the tree
        constructTree(0, n - 1, 0, a);
      
        // 1st query
        int index = 0;
        int value = 2;
        updateValue(index, value, a, n);
        System.out.println(tree[0]);
      
        // 2nd query
        index = 3;
        value = 5;
        updateValue(index, value, a, n);
        System.out.println(tree[0]);
    }
}
  
// This code is contributed by vt_m.

Python3

# Python3 program to print the Leftover element 
# after performing alternate Bitwise OR and 
# Bitwise XOR operations to the pairs. 
N = 1000 
  
# array to store the tree 
tree = [None] * N
  
# array to store the level of every parent 
level = [None] * N 
  
# function to construct the tree 
def constructTree(low, high, pos, a): 
   
    if low == high:
       
        # level of child is always 0 
        level[pos], tree[pos] = 0, a[high]
        return 
       
    mid = (low + high) // 2 
  
    # Recursive call 
    constructTree(low, mid, 2 * pos + 1, a) 
    constructTree(mid + 1, high, 2 * pos + 2, a) 
  
    # Increase the level of every parent, 
    # which is level of child + 1 
    level[pos] = level[2 * pos + 1] + 1 
  
    # If the parent is at odd level, 
    # then do a bitwise OR 
    if level[pos] & 1: 
        tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2] 
  
    # If the parent is at even level, 
    # then do a bitwise XOR 
    else:
        tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2] 
   
# Function that updates the tree 
def update(low, high, pos, index, a): 
   
    # If it is a leaf and the leaf 
    # which is to be updated 
    if low == high and low == index: 
       
        tree[pos] = a[low] 
        return 
       
    # out of range 
    if index < low or index > high: 
        return 
  
    # not a leaf then recurse 
    if low != high: 
       
        mid = (low + high) // 2 
  
        # recursive call 
        update(low, mid, 2 * pos + 1, index, a) 
        update(mid + 1, high, 2 * pos + 2, index, a) 
  
        # check if the parent is at odd or even level 
        # and perform OR or XOR according to that 
        if level[pos] & 1:
            tree[pos] = tree[2 * pos + 1] | tree[2 * pos + 2] 
        else:
            tree[pos] = tree[2 * pos + 1] ^ tree[2 * pos + 2] 
  
# Function that assigns value to a[index] 
# and calls update function to update the tree 
def updateValue(index, value, a, n): 
   
    a[index] = value 
    update(0, n - 1, 0, index, a) 
   
# Driver Code 
if __name__ == "__main__":
   
    a = [1, 4, 5, 6] 
    n = len(a) 
  
    # builds the tree 
    constructTree(0, n - 1, 0, a) 
  
    # 1st query 
    index, value = 0, 2 
    updateValue(index, value, a, n) 
    print(tree[0]) 
  
    # 2nd query 
    index, value = 3, 5 
    updateValue(index, value, a, n) 
    print(tree[0])
   
# This code is contributed by Rituraj Jain

C#

// C# program to print the Leftover
// element after performing alternate
// Bitwise OR and Bitwise XOR
// operations to the pairs.
using System;
  
public class GFG {
  
    static int N = 1000;
      
    // array to store the tree
    static int []tree = new int[N];
      
    // array to store the level of
    // every parent
    static int []level = new int[N];
      
    // function to construct the
    // tree
    static void constructTree(int low, int high,
                               int pos, int []a)
    {
        if (low == high)
        {
              
            // level of child is always 0
            level[pos] = 0;
            tree[pos] = a[high];
            return;
        }
        int mid = (low + high) / 2;
      
        // recursive call
        constructTree(low, mid, 2 * pos + 1, a);
          
        constructTree(mid + 1, high,
                                2 * pos + 2, a);
      
        // increase the level of every parent,
        // which is level of child + 1
        level[pos] = level[2 * pos + 1] + 1;
      
        // if the parent is at odd level,
        // then do a bitwise OR
        if ((level[pos] & 1) > 0)
            tree[pos] = tree[2 * pos + 1] |
                           tree[2 * pos + 2];
      
        // if the parent is at even level,
        // then do a bitwise XOR
        else
            tree[pos] = tree[2 * pos + 1] ^
                          tree[2 * pos + 2];
    }
      
    // function that updates the tree
    static void update(int low, int high,
               int pos, int index, int []a)
    {
          
        // if it is a leaf and the leaf
        // which is to be updated
        if (low == high && low == index)
        {
            tree[pos] = a[low];
            return;
        }
      
        // out of range
        if (index < low || index > high)
            return;
      
        // not a leaf then recurse
        if (low != high)
        {
            int mid = (low + high) / 2;
      
            // recursive call
            update(low, mid, 2 * pos + 1,
                                   index, a);
                                     
            update(mid + 1, high, 2 * pos + 2,
                                    index, a);
      
            // check if the parent is at odd
            // or even level and perform OR
            // or XOR according to that
            if ((level[pos] & 1) > 0)
                tree[pos] = tree[2 * pos + 1] |
                              tree[2 * pos + 2];
            else
                tree[pos] = tree[2 * pos + 1]
                            ^ tree[2 * pos + 2];
        }
    }
      
    // function that assigns value to a[index]
    // and calls update function to update
    // the tree
    static void updateValue(int index, int value,
                                 int []a, int n)
    {
        a[index] = value;
        update(0, n - 1, 0, index, a);
    }
      
    // Driver Code
    static public void Main ()
    {
        int []a = { 1, 4, 5, 6 };
        int n = a.Length;;
      
        // builds the tree
        constructTree(0, n - 1, 0, a);
      
        // 1st query
        int index = 0;
        int value = 2;
        updateValue(index, value, a, n);
        Console.WriteLine(tree[0]);
      
        // 2nd query
        index = 3;
        value = 5;
        updateValue(index, value, a, n);
        Console.WriteLine(tree[0]);
    }
}
  
// This code is contributed by vt_m.

Javascript

<script>    
    // Javascript program to print the Leftover
    // element after performing alternate
    // Bitwise OR and Bitwise XOR
    // operations to the pairs.
      
    let N = 1000;
       
    // array to store the tree
    let tree = new Array(N);
    tree.fill(0);
       
    // array to store the level of
    // every parent
    let level = new Array(N);
    level.fill(0);
       
    // function to construct the
    // tree
    function constructTree(low, high, pos, a)
    {
        if (low == high)
        {
               
            // level of child is always 0
            level[pos] = 0;
            tree[pos] = a[high];
            return;
        }
        let mid = parseInt((low + high) / 2, 10);
       
        // recursive call
        constructTree(low, mid, 2 * pos + 1, a);
           
        constructTree(mid + 1, high, 2 * pos + 2, a);
       
        // increase the level of every parent,
        // which is level of child + 1
        level[pos] = level[2 * pos + 1] + 1;
       
        // if the parent is at odd level,
        // then do a bitwise OR
        if ((level[pos] & 1) > 0)
            tree[pos] = tree[2 * pos + 1] |
                           tree[2 * pos + 2];
       
        // if the parent is at even level,
        // then do a bitwise XOR
        else
            tree[pos] = tree[2 * pos + 1] ^
                          tree[2 * pos + 2];
    }
       
    // function that updates the tree
    function update(low, high, pos, index, a)
    {
           
        // if it is a leaf and the leaf
        // which is to be updated
        if (low == high && low == index)
        {
            tree[pos] = a[low];
            return;
        }
       
        // out of range
        if (index < low || index > high)
            return;
       
        // not a leaf then recurse
        if (low != high)
        {
            let mid = parseInt((low + high) / 2, 10);
       
            // recursive call
            update(low, mid, 2 * pos + 1,
                                   index, a);
                                      
            update(mid + 1, high, 2 * pos + 2,
                                    index, a);
       
            // check if the parent is at odd
            // or even level and perform OR
            // or XOR according to that
            if ((level[pos] & 1) > 0)
                tree[pos] = tree[2 * pos + 1] |
                              tree[2 * pos + 2];
            else
                tree[pos] = tree[2 * pos + 1]
                            ^ tree[2 * pos + 2];
        }
    }
       
    // function that assigns value to a[index]
    // and calls update function to update
    // the tree
    function updateValue(index, value, a, n)
    {
        a[index] = value;
        update(0, n - 1, 0, index, a);
    }
      
    let a = [ 1, 4, 5, 6 ];
    let n = a.length;;
  
    // builds the tree
    constructTree(0, n - 1, 0, a);
  
    // 1st query
    let index = 0;
    let value = 2;
    updateValue(index, value, a, n);
    document.write(tree[0] + "</br>");
  
    // 2nd query
    index = 3;
    value = 5;
    updateValue(index, value, a, n);
    document.write(tree[0]);
      
</script>

Producción: 

1
3

Complejidad del tiempo :  

  • Construcción del árbol: O(N)
  • Consulta de respuesta: O (log 2 N)

Complejidad espacial : O(N)

Publicación traducida automáticamente

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