Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 23 of 32

Range Bitwise Queries

May 2026 · 24 min read

Range bitwise problems look similar to range sum problems, but AND, OR, and XOR each have different algebra. XOR has inverses and works beautifully with prefixes. AND and OR are idempotent and monotonic, so they pair well with sparse tables, segment trees, and binary search.

Prefix XOR

XOR is its own inverse, so range XOR is exactly like prefix sum with subtraction replaced by XOR.

pref[0] = 0;
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] ^ a[i];

int range_xor(int l, int r) {
    return pref[r + 1] ^ pref[l];
}

Range AND and OR

AND only loses 1-bits as the range expands. OR only gains 1-bits as the range expands. This monotonicity is useful for two-pointers and binary search.

Bit-Count Prefix Arrays

For each bit, count how many values in a range have that bit set. This reconstructs range OR and AND quickly.

int cnt[32][N + 1];
for (int b = 0; b < 32; ++b) {
    for (int i = 0; i < n; ++i) {
        cnt[b][i + 1] = cnt[b][i] + ((a[i] >> b) & 1);
    }
}

int range_or(int l, int r) {
    int len = r - l + 1, ans = 0;
    for (int b = 0; b < 32; ++b)
        if (cnt[b][r + 1] - cnt[b][l] > 0) ans |= 1 << b;
    return ans;
}

int range_and(int l, int r) {
    int len = r - l + 1, ans = 0;
    for (int b = 0; b < 32; ++b)
        if (cnt[b][r + 1] - cnt[b][l] == len) ans |= 1 << b;
    return ans;
}

Sparse Table

AND and OR are idempotent: x & x = x and x | x = x. That means overlapping sparse table intervals are safe.

int query_and(int l, int r) {
    int k = lg[r - l + 1];
    return st[k][l] & st[k][r - (1 << k) + 1];
}

Segment Tree

Use a segment tree when updates are present. The merge function is simply AND, OR, or XOR depending on the query.

int merge(int left, int right) {
    return left | right; // or &, or ^
}

Practice Problems