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) = 7Entrada: arr[] = {4, 0, 1, 2}, Q[][] = {{1, 3}}
Salida: 3
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