Bounded Range Segment Evaluator — Problem Statement & Solution Guide

TreesMediumTrie XOR Maximum

TimeO(N·log N·log MAX + Q·log N·log MAX)

SpaceO(N·log MAX)

Problem Description

You are given an array of N signed 32‑bit integers. For each of Q queries you receive two indices L and R (1‑based, inclusive). For the subarray nums[L..R] you must determine the largest value that can be obtained by XORing two distinct elements from that subarray. Output the maximum XOR for each query on a separate line. The task is to answer all queries efficiently, as the array and the number of queries can be large.

DSA Pattern Breakdown

"Bounded Range Segment Evaluator"

medium

WHY DOES IT MATTER?

Range‑maximum‑XOR is a representative of the "offline range query with complex combine" pattern. Mastering it teaches you how to embed a non‑linear data structure (binary trie) inside a segment tree, a skill that recurs in problems involving bitwise metrics, nearest‑greater queries, and geometric nearest‑pair calculations.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that the maximum XOR of two numbers can be found by walking a binary trie, and that the trie can be merged lazily during a query by always iterating over the smaller side. This reduces the naïve O(k·log MAX) per node to O(min(|A|,|B|)·log MAX), keeping the total per query at O(log N·log MAX).

REAL-WORLD CONNECTION

Think of a distributed cache where each node stores a compressed summary (the trie) of the keys it holds. To answer a global request (max XOR across shards), the coordinator merges summaries instead of pulling all raw keys, dramatically reducing bandwidth—exactly what the segment‑tree‑trie does for subarray queries.

When implementing, store the trie nodes in a pool (pre‑allocated array) to avoid frequent allocations, and keep the size of each node’s subtree (count) so you can quickly decide which side is smaller during cross‑pair evaluation.

COMPLEXITY AT A GLANCE

⏱ Time:O(N·log N·log MAX + Q·log N·log MAX)

💾 Space:O(N·log MAX)

Core Theory — Why This Approach?

The maximum XOR of two distinct elements in a subarray is a classic range‑query problem that cannot be solved by scanning the interval for each query because the naïve O(N) per query leads to O(N·Q) time, which explodes for N, Q up to 2·10^5. The optimal paradigm combines a divide‑and‑conquer segment tree with a binary trie (also called a prefix tree) that stores the binary representation of the numbers in each segment. Each node of the segment tree keeps two pieces of information: (1) a binary trie containing all values of its segment, enabling O(⌈log MAX⌉) lookup of the best partner for any value, and (2) the pre‑computed maximum XOR achievable entirely inside that segment. When answering a query, the segment tree returns O(log N) nodes whose intervals partition the requested range. The overall answer is the maximum among (a) the stored node‑answers and (b) the best cross‑pair between any two of those nodes, which can be obtained by querying the smaller node’s values against the larger node’s trie. This yields an overall O((log N)·log MAX) per query after an O(N·log N·log MAX) build, comfortably within the limits for medium‑difficulty constraints.

Interview Questions on This Problem

Q1How would you modify the solution if the query asked for the maximum AND instead of XOR?

Maximum AND can be tackled by a similar segment‑tree‑with‑bit‑set approach, but instead of a binary trie we store the count of set bits at each position. For a query we greedily try to keep a bit set in the answer only if at least two numbers in the range have that bit set. This can be answered in O(30) per query using a segment tree that maintains bit‑frequency vectors.

Q2Can you answer the same problem online (queries interleaved with updates) and what data structure would you use?

Yes. Use a segment tree where each leaf holds a binary trie of size 1. On point updates we rebuild the leaf’s trie and recompute the parent’s trie and max‑XOR in O(log MAX) per level, giving O(log N·log MAX) per update and query.

Q3Why does a linear basis (XOR basis) not give the correct answer for maximum pair XOR in a range?

A linear basis yields the maximum XOR achievable by any subset of the numbers, which may involve three or more elements. The maximum pair XOR is constrained to exactly two elements, and the basis can produce a larger value by XOR‑ing more than two numbers, so it overestimates the answer.

Examples

Example 1

Input

Output

3
7

Explanation: For the first query the subarray is [1,2,3]. The XORs are 1^2=3, 1^3=2, 2^3=1, so the maximum is 3. For the second query the subarray is [2,3,4,5]. The XORs are 2^5=7, 3^4=7, 4^5=1, etc.; the largest value is 7.

Example 2

Input

Output

Explanation: All pairs in the whole array are considered. The XORs are 8^1=9, 8^2=10, 8^3=11, 1^2=3, 1^3=2, 2^3=1. The maximum is 11.

Example 3

Input

6
0 7 14 21 28 35
3
1 6
2 4
3 5

Output

35
31
31

Explanation: Query 1: subarray [0,7,14,21,28,35] – the pair 0^35 gives 35, which is the largest. Query 2: subarray [7,14,21] – 14^21=31 is the maximum. Query 3: subarray [14,21,28] – 14^21=31 is again the maximum.

Example 4

Input

Output

Explanation: Using 32‑bit two’s complement representation, the XORs are -1^(-2)=1, -1^(-3)=2, -2^(-3)=1. The largest XOR value is 2.

Constraints

1 <= N <= 100000
1 <= Q <= 100000
-1000000000 <= nums[i] <= 1000000000
1 <= L <= R <= N
All calculations fit within signed 32‑bit integers

Optimal Approach & Strategy

Build a segment tree; each node holds a binary trie of its segment and the node's maximum XOR. Answer a query by merging O(log N) nodes, using trie look‑ups to evaluate cross‑segment pairs in O(log MAX) each.

Brute Force Approach

For each query, iterate over all pairs (i, j) with L ≤ i < j ≤ R and compute nums[i] XOR nums[j]; keep the maximum.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N·log N·log MAX + Q·log N·log MAX)

function solution(nums) {
   let root = {};
   let xor = 0;
   for (let num of nums) {
       let node = root;
       for (let bit = 31; bit >= 0; bit--) {
           let currBit = (num >> bit) & 1;
           if (!node[currBit]) node[currBit] = {};
           node = node[currBit];
           xor ^= num;
       }
       node.xor = xor;
   }
   let result = 0;
   for (let node of Object.values(root)) {
       result ^= node.xor;
   }
   return result;
}

class Solution {
   public:
   int solution(vector<int>& nums) {
       unordered_map<int, unordered_map<int, unordered_map<int, int>>> root;
       int xor = 0;
       for (int num : nums) {
           unordered_map<int, unordered_map<int, int>> node = root;
           for (int bit = 31; bit >= 0; bit--) {
               int currBit = (num >> bit) & 1;
               if (node.find(currBit) == node.end()) node[currBit] = {};
               node = node[currBit];
               xor ^= num;
           }
           node['xor'] = xor;
       }
       int result = 0;
       for (auto& node : root) {
           result ^= node.second.find('xor')->second;
       }
       return result;
   }
}

class Solution {
   public int solution(int[] nums) {
       Map<Integer, Map<Integer, Map<Integer, Integer>>> root = new HashMap<>();
       int xor = 0;
       for (int num : nums) {
           Map<Integer, Map<Integer, Integer>> node = root;
           for (int bit = 31; bit >= 0; bit--) {
               int currBit = (num >> bit) & 1;
               if (!node.containsKey(currBit)) node.put(currBit, new HashMap<>());
               node = node.get(currBit);
               xor ^= num;
           }
           node.put('xor', xor);
       }
       int result = 0;
       for (Map<Integer, Map<Integer, Integer>> node : root.values()) {
           result ^= node.get('xor');
       }
       return result;
   }
}

def solution(nums):
   root = {}
   xor = 0
   for num in nums:
       node = root
       for bit in range(31, -1, -1):
           curr_bit = (num >> bit) & 1
           if curr_bit not in node:
               node[curr_bit] = {}
           node = node[curr_bit]
           xor ^= num
       node['xor'] = xor
   result = 0
   for node in root.values():
       result ^= node.get('xor', 0)
   return result

function solution(nums) {
   let root = {};
   let xor = 0;
   for (let num of nums) {
       let node = root;
       for (let bit = 31; bit >= 0; bit--) {
           let currBit = (num >> bit) & 1;
           if (!node[currBit]) node[currBit] = {};
           node = node[currBit];
           xor ^= num;
       }
       node.xor = xor;
   }
   let result = 0;
   for (let node of Object.values(root)) {
       result ^= node.xor;
   }
   return result;
}

Asked in Top Tech Interviews

CredAccenture

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Bounded Range Segment Evaluator Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Trees

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Bounded Range Segment Evaluator — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor