Consultas para evaluar la ecuación dada en un rango [L, R]

Dada una array arr[] que consta de N enteros y consultas Q[][] de la forma {L, R} donde 0 ≤ L < R ≤ N – 1 , la tarea para cada consulta es calcular la siguiente ecuación:

K L | K L + 1 |…| K R – 1 
donde K i = (arr[i] ^ arr[i+1]) | (arr[i] ~ arr[i+1])
“~” representa XNOR binario , 
“^” representa XOR binario , 
“|” representa O binario 
 

Ejemplos:

Entrada: arr[] = {5, 2, 3, 0}, Q[][] = {{1, 3}, {0, 2}} 
Salida: 3 7 
Explicación: 
Consulta 1: L = 1, R = 3 : K 1 = (2 ^ 3) | (2 ~ 3) = (3 | 2) = 3, K 2 = (3 ^ 0) | (3 ~ 0) = (3 | 0) = 3. 
Por lo tanto, K 1 | K 2 = (3 | 3) = 3 
Consulta 2: L = 0, R = 2 : K 0 = 7, K 1 = 3. 
Por lo tanto, K 0 | K 1 = (7 | 3) = 7

Entrada: arr[] = {4, 0, 1, 2}, Q[][] = {{1, 3}} 
Salida:
 

Enfoque ingenuo: el enfoque más simple para resolver este problema es recorrer los índices [L, R – 1] y, para cada elemento, calcular K i , donde L ≤ i < R .

Complejidad de tiempo: O (N * tamaño de (Q))

Enfoque eficiente : para optimizar el enfoque anterior, la idea es utilizar un árbol de segmentos o una tabla dispersa . Siga los pasos a continuación para resolver el problema:

  • Es necesario hacer la siguiente observación:

La operación XOR establece solo aquellos bits que están establecidos en arri o en arr i +1 XNOR establece aquellos bits que están establecidos tanto en ai como en ai+1 o no establecidos en ambos. 

  • Tomando OR de ambas operaciones, se establecerán todos los bits hasta el mayor de max(MSB(arr i ), MSB(arr i+1 )) .
  • Por lo tanto, encuentre el número más grande, utilizando Segment Tree, entre los índices dados y establezca todos sus bits en 1, para obtener la respuesta requerida.
  • Imprime la respuesta.

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 obtain the
// middle index of the range
int getMid(int s, int e)
{
    return s + (e - s) / 2;
}
  
/* Recursive function to get the sum of 
   values in the given range from the array. 
   The following are parameters for this 
   function. 
  
    st     -> Pointer to segment tree 
  
    node     -> Index of current node in 
                the segment tree
  
    ss & se -> Starting and ending indexes 
               of the segment represented 
               by current node, i.e., st[node] 
  
    l & r -> Starting and ending indexes 
             of range query */
int MaxUtil(int* st, int ss, int se, int l,
            int r, int node)
{
    // If the segment of this node lies
    // completely within the given range
    if (l <= ss && r >= se)
  
        // Return maximum in the segment
        return st[node];
  
    // If the segment of this node lies
    // outside the given range
    if (se < l || ss > r)
        return -1;
  
    // If segment of this node lies
    // partially in the given range
    int mid = getMid(ss, se);
  
    return max(MaxUtil(st, ss, mid, l, r,
                       2 * node + 1),
               MaxUtil(st, mid + 1, se, l,
                       r, 2 * node + 2));
}
  
// Function to return the maximum in the
// range from [l, r]
int getMax(int* st, int n, int l, int r)
{
    // Check for erroneous input values
    if (l < 0 || r > n - 1 || l > r) {
        printf("Invalid Input");
        return -1;
    }
  
    return MaxUtil(st, 0, n - 1, l, r, 0);
}
  
// Function to construct Segment Tree
// for the subarray [ss..se]
int constructSTUtil(int arr[], int ss, int se,
                    int* st, int si)
{
    // For a single element
    if (ss == se) {
        st[si] = arr[ss];
        return arr[ss];
    }
  
    // Otherwise
    int mid = getMid(ss, se);
  
    // Recur for left subtree
    st[si] = max(constructSTUtil(arr, ss, mid, st,
                                 si * 2 + 1),
  
                 // Recur for right subtree
                 constructSTUtil(arr, mid + 1, se,
                                 st, si * 2 + 2));
  
    return st[si];
}
  
// Function to construct Segment Tree from
// the given array
int* constructST(int arr[], int n)
{
    // 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];
  
    // Fill the allocated memory
    constructSTUtil(arr, 0, n - 1, st, 0);
  
    // Return the constructed Segment Tree
    return st;
}
  
// Driver Code
int main()
{
    int arr[] = { 5, 2, 3, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Build the Segment Tree
    // from the given array
    int* st = constructST(arr, n);
  
    vector<vector<int> > Q = { { 1, 3 }, { 0, 2 } };
    for (int i = 0; i < Q.size(); i++) {
  
        int max = getMax(st, n, Q[i][0], Q[i][1]);
        int ok = 0;
        for (int i = 30; i >= 0; i--) {
            if ((max & (1 << i)) != 0)
                ok = 1;
  
            if (!ok)
                continue;
  
            max |= (1 << i);
        }
  
        cout << max << " ";
    }
  
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
  
// Function to obtain the
// middle index of the range
static int getMid(int s, int e)
{
    return s + (e - s) / 2;
}
  
/* Recursive function to get the sum of 
   values in the given range from the array. 
   The following are parameters for this 
   function. 
  
    st    .Pointer to segment tree 
  
    node    .Index of current node in 
                the segment tree
  
    ss & se.Starting and ending indexes 
               of the segment represented 
               by current node, i.e., st[node] 
  
    l & r.Starting and ending indexes 
             of range query */
static int MaxUtil(int[] st, int ss, 
                   int se, int l, 
                   int r, int node)
{
    // If the segment of this node lies
    // completely within the given range
    if (l <= ss && r >= se)
  
        // Return maximum in the segment
        return st[node];
  
    // If the segment of this node lies
    // outside the given range
    if (se < l || ss > r)
        return -1;
  
    // If segment of this node lies
    // partially in the given range
    int mid = getMid(ss, se);
  
    return Math.max(MaxUtil(st, ss, mid, l, r,
                                2 * node + 1),
                       MaxUtil(st, mid + 1, se, l,
                             r, 2 * node + 2));
}
  
// Function to return the maximum in the
// range from [l, r]
static int getMax(int []st, int n,
                  int l, int r)
{
    // Check for erroneous input values
    if (l < 0 || r > n - 1 || l > r)
    {
        System.out.printf("Invalid Input");
        return -1;
    }
  
    return MaxUtil(st, 0, n - 1, l, r, 0);
}
  
// Function to construct Segment Tree
// for the subarray [ss..se]
static int constructSTUtil(int arr[], int ss, 
                           int se, int[] st,
                           int si)
{
    // For a single element
    if (ss == se) 
    {
        st[si] = arr[ss];
        return arr[ss];
    }
  
    // Otherwise
    int mid = getMid(ss, se);
  
    // Recur for left subtree
    st[si] = Math.max(constructSTUtil(arr, ss, mid, st,
                                            si * 2 + 1),
  
                      // Recur for right subtree
                      constructSTUtil(arr, mid + 1, se,
                                       st, si * 2 + 2));
  
    return st[si];
}
  
// Function to construct Segment Tree from
// the given array
static int[] constructST(int arr[], int n)
{
    // Height of Segment Tree
    int x = (int)(Math.ceil(Math.log(n)));
  
    // Maximum size of Segment Tree
    int max_size = 2 * (int)Math.pow(2, x) - 1;
  
    // Allocate memory
    int []st = new int[max_size];
  
    // Fill the allocated memory
    constructSTUtil(arr, 0, n - 1, st, 0);
  
    // Return the constructed Segment Tree
    return st;
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 2, 3, 0 };
    int n = arr.length;
  
    // Build the Segment Tree
    // from the given array
    int []st = constructST(arr, n);
  
    int[][] Q = { { 1, 3 }, { 0, 2 } };
    for (int i = 0; i < Q.length; i++) 
    {
        int max = getMax(st, n, Q[i][0], Q[i][1]);
        int ok = 0;
        for (int j = 30; j >= 0; j--) 
        {
            if ((max & (1 << j)) != 0)
                ok = 1;
  
            if (ok<=0)
                continue;
  
            max |= (1 << j);
        }
        System.out.print(max+ " ");
    }
}
}
  
// This code is contributed by gauravrajput1

Python3

# Python3 program to implement
# the above approach
import math
  
# Function to obtain the
# middle index of the range
def getMid(s, e):
      
    return (s + (e - s) // 2)
  
def MaxUtil(st, ss, se, l, r, node):
      
    # If the segment of this node lies
    # completely within the given range
    if (l <= ss and r >= se):
          
        # Return maximum in the segment
        return st[node]
  
    # If the segment of this node lies
    # outside the given range
    if (se < l or ss > r):
        return -1
  
    # If segment of this node lies
    # partially in the given range
    mid = getMid(ss, se)
  
    return max(MaxUtil(st, ss, mid, l, 
                       r, 2 * node + 1), 
               MaxUtil(st, mid + 1, se, 
                       l, r, 2 * node + 2))
  
# Function to return the maximum
# in the range from [l, r]
def getMax(st, n, l, r):
      
    # Check for erroneous input values
    if (l < 0 or r > n - 1 or l > r):
        print("Invalid Input")
        return -1
      
    return MaxUtil(st, 0, n - 1, l, r, 0)
  
# Function to construct Segment Tree
# for the subarray [ss..se]
def constructSTUtil(arr, ss, se, st, si):
  
    # For a single element
    if (ss == se):
        st[si] = arr[ss]
        return arr[ss]
  
    # Otherwise
    mid = getMid(ss, se)
  
    # Recur for left subtree
    st[si] = max(constructSTUtil(arr, ss, mid, st,
                                 si * 2 + 1),
                 constructSTUtil(arr, mid + 1, se, 
                                 st, si * 2 + 2))
    return st[si]
  
# Function to construct Segment Tree
# from the given array
def constructST(arr, n):
  
    # Height of Segment Tree
    x = (int)(math.ceil(math.log(n)))
  
    # Maximum size of Segment Tree
    max_size = 2 * (int)(pow(2, x)) - 1
  
    # Allocate memory
    st = [0] * max_size
  
    # Fill the allocated memory
    constructSTUtil(arr, 0, n - 1, st, 0)
  
    # Return the constructed Segment Tree
    return st
  
# Driver Code
arr = [ 5, 2, 3, 0 ]
n = len(arr)
  
# Build the Segment Tree
# from the given array
st = constructST(arr, n)
  
Q = [ [ 1, 3 ], [ 0, 2 ] ]
for i in range(len(Q)):
    Max = getMax(st, n, Q[i][0], Q[i][1])
    ok = 0
      
    for j in range(30, -1, -1):
        if ((Max & (1 << j)) != 0):
            ok = 1
  
        if (ok <= 0):
            continue
  
        Max |= (1 << j)
      
    print(Max, end = " ")
  
# This code is contributed by divyesh072019

C#

// C# Program to implement
// the above approach
using System;
class GFG {
  
    // Function to obtain the
    // middle index of the range
    static int getMid(int s, int e)
    {
        return s + (e - s) / 2;
    }
  
    /* Recursive function to get the sum of
    values in the given range from the array.
    The following are parameters for this
    function:
    st--> Pointer to segment tree
    node--> Index of current node
    in segment tree
    ss & se--> Starting and ending indexes
    of the segment represented
    by current node, i.e., st[node]
    l & r--> Starting and ending indexes
    of range query */
    static int MaxUtil(int[] st, int ss, int se, 
                       int l, int r, int node)
    {
  
        // If the segment of this node lies
        // completely within the given range
        if (l <= ss && r >= se)
  
            // Return maximum in the segment
            return st[node];
  
        // If the segment of this node lies
        // outside the given range
        if (se < l || ss > r)
            return -1;
  
        // If segment of this node lies
        // partially in the given range
        int mid = getMid(ss, se);
  
        return Math.Max(
            MaxUtil(st, ss, mid, l, r, 2 * node + 1),
            MaxUtil(st, mid + 1, se, l, r, 2 * node + 2));
    }
  
    // Function to return the maximum
    // in the range from [l, r]
    static int getMax(int[] st, int n, int l, int r)
    {
        // Check for erroneous input values
        if (l < 0 || r > n - 1 || l > r) 
        {
            Console.Write("Invalid Input");
            return -1;
        }
        return MaxUtil(st, 0, n - 1, l, r, 0);
    }
  
    // Function to construct Segment Tree
    // for the subarray [ss..se]
    static int constructSTUtil(int[] arr, int ss, int se,
                               int[] st, int si)
    {
        // For a single element
        if (ss == se) 
        {
            st[si] = arr[ss];
            return arr[ss];
        }
  
        // Otherwise
        int mid = getMid(ss, se);
  
        // Recur for left subtree
        st[si] = Math.Max(
            constructSTUtil(arr, ss, mid, st, 
                            si * 2 + 1),
  
            // Recur for right subtree
            constructSTUtil(arr, mid + 1, se, st,
                            si * 2 + 2));
        return st[si];
    }
  
    // Function to construct Segment Tree
    // from the given array
    static int[] constructST(int[] arr, int n)
    {
        // Height of Segment Tree
        int x = (int)(Math.Ceiling(Math.Log(n)));
  
        // Maximum size of Segment Tree
        int max_size = 2 * (int)Math.Pow(2, x) - 1;
  
        // Allocate memory
        int[] st = new int[max_size];
  
        // Fill the allocated memory
        constructSTUtil(arr, 0, n - 1, st, 0);
  
        // Return the constructed Segment Tree
        return st;
    }
  
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = {5, 2, 3, 0};
        int n = arr.Length;
  
        // Build the Segment Tree
        // from the given array
        int[] st = constructST(arr, n);
  
        int[, ] Q = {{1, 3}, {0, 2}};
        for (int i = 0; i < Q.GetLength(0); i++) {
            int max = getMax(st, n, Q[i, 0], Q[i, 1]);
            int ok = 0;
            for (int j = 30; j >= 0; j--) {
                if ((max & (1 << j)) != 0)
                    ok = 1;
  
                if (ok <= 0)
                    continue;
  
                max |= (1 << j);
            }
            Console.Write(max + " ");
        }
    }
}
  
// This code is contributed by Amit Katiyar

Javascript

<script>
  
// JavaScript program for the above approach
   
// Function to obtain the
// middle index of the range
function getMid(s, e)
{
    return (s + Math.floor((e - s) / 2));
}
   
/* Recursive function to get the sum of
   values in the given range from the array.
   The following are parameters for this
   function.
   
    st    .Pointer to segment tree
   
    node    .Index of current node in
                the segment tree
   
    ss & se.Starting and ending indexes
               of the segment represented
               by current node, i.e., st[node]
   
    l & r.Starting and ending indexes
             of range query */
function MaxUtil(st, ss,
                   se, l,
                   r, node)
{
    // If the segment of this node lies
    // completely within the given range
    if (l <= ss && r >= se)
   
        // Return maximum in the segment
        return st[node];
   
    // If the segment of this node lies
    // outside the given range
    if (se < l || ss > r)
        return -1;
   
    // If segment of this node lies
    // partially in the given range
    let mid = getMid(ss, se);
   
    return Math.max(MaxUtil(st, ss, mid, l, r,
                                2 * node + 1),
                       MaxUtil(st, mid + 1, se, l,
                             r, 2 * node + 2));
}
   
// Function to return the maximum in the
// range from [l, r]
function getMax(st, n, l, r)
{
    // Check for erroneous input values
    if (l < 0 || r > n - 1 || l > r)
    {
        document.write("Invalid Input");
        return -1;
    }
   
    return MaxUtil(st, 0, n - 1, l, r, 0);
}
   
// Function to construct Segment Tree
// for the subarray [ss..se]
function constructSTUtil(arr, ss, se, st,
                           si)
{
    // For a single element
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }
   
    // Otherwise
    let mid = getMid(ss, se);
   
    // Recur for left subtree
    st[si] = Math.max(constructSTUtil(arr, ss, mid, st,
                                            si * 2 + 1),
   
                      // Recur for right subtree
                      constructSTUtil(arr, mid + 1, se,
                                       st, si * 2 + 2));
   
    return st[si];
}
   
// Function to construct Segment Tree from
// the given array
function constructST(arr, n)
{
    // Height of Segment Tree
    let x = (Math.ceil(Math.log(n)));
   
    // Maximum size of Segment Tree
    let max_size = 2 * Math.pow(2, x) - 1;
   
    // Allocate memory
    let st = Array.from({length: max_size}, (_, i) => 0); 
   
    // Fill the allocated memory
    constructSTUtil(arr, 0, n - 1, st, 0);
   
    // Return the constructed Segment Tree
    return st;
}
      
// Driver Code
      
    let arr = [ 5, 2, 3, 0 ];
    let n = arr.length;
   
    // Build the Segment Tree
    // from the given array
    let st = constructST(arr, n);
   
    let Q = [[ 1, 3 ], [ 0, 2 ]];
    for (let i = 0; i < Q.length; i++)
    {
        let max = getMax(st, n, Q[i][0], Q[i][1]);
        let ok = 0;
        for (let j = 30; j >= 0; j--)
        {
            if ((max & (1 << j)) != 0)
                ok = 1;
   
            if (ok<=0)
                continue;
   
            max |= (1 << j);
        }
        document.write(max+ " ");
    }
       
</script>
Producción: 

3 7

 

Complejidad de tiempo: O(N*log(tamaño(Q))  
Espacio auxiliar: O(N)

Tema relacionado: Árbol de segmentos

Publicación traducida automáticamente

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