Segment Trees

Segment trees are versatile data structures used for storing and querying information about intervals or segments efficiently. We can build a segment tree for the given range and then use it to query the XOR of numbers in the range.

Example: Let us consider an example where we have L=5 and R=15. We will build a segment tree for the range [5, 15] and then query it to find the XOR of numbers from 5 to 15.

JavaScript

// Segment Tree
function updateSegmentTree(tree, index, val, node, start, end) {
    if (start === end) {
        tree[node] ^= val;
        return;
    }

    let mid = Math.floor((start + end) / 2);
    if (index <= mid) {
        updateSegmentTree(tree, index, val, 2 * node, start, mid);
    } else {
        updateSegmentTree(tree, index, val, 2 * node + 1, mid + 1, end);
    }
    tree[node] = tree[2 * node] ^ tree[2 * node + 1];
}

// Query Segment Tree
function querySegmentTree(tree, left, right, node, start, end) {
    if (right < start || left > end) {
        return 0;
    }
    if (left <= start && right >= end) {
        return tree[node];
    }

    let mid = Math.floor((start + end) / 2);
    let leftXor = querySegmentTree(tree, left, right, 2 * node, start, mid);
    let rightXor = querySegmentTree(tree, left, right, 2 * node + 1, mid + 1, end);
    return leftXor ^ rightXor;
}

function xorRange(L, R) {
    // Build Segment Tree
    const n = R - L + 1;
    const tree = new Array(4 * n).fill(0);
    for (let i = L; i <= R; i++) {
        updateSegmentTree(tree, i - L + 1, i, 1, 1, n);
    }

    // Query Segment Tree
    return querySegmentTree(tree, 1, n, 1, 1, n);
}

const L = 5;
const R = 15;
const result = xorRange(L, R);
console.log(`Bitwise XOR of all numbers from ${L} to ${R} is ${result}`);

Output:

Bitwise XOR of all numbers from 5 to 15 is 4

Time Complexity: O(N) , where N is the number of elements in the array. Querying the segment tree takes O(log N) time.

Space Complexity: O(N) for storing the tree structure.

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

The complexity of bitwise XOR computation for all the numbers in a specific range is the most frequent difficulty that many people face during the problem-solving process.

Problem Description: Given two integers, L and R, find the bitwise XOR of all numbers in the inclusive range from L to R. There are several approaches to computing the bitwise XOR of all numbers in a range using JavaScript which are as follows:

Table of Content

Bitwise XOR Property
Segment Trees
Binary Indexed Trees (Fenwick Trees)
Bitwise Manipulation

Tags:

#JavaScript #Web Technologies

Bitwise XOR Property

Binary Indexed Trees (Fenwick Trees)

Segment Trees

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

Similar Reads

Contact Us