Author: Abu Sufian Rafi
Problem tag: Bitmasks, Combinatorics, Range queries
Editorial:
For an array segment of size m, there are 2^m possible subsequences (including the empty one). For each bit position b, we determine how often that bit contributes to the total XOR across all subsequences.
Let:

• cnt1 = number of elements with the b-th bit set
• cnt0 = number of elements with the b-th bit unset (cnt0 = m - cnt1)

We know the b-th bit contributes to a subsequence XOR only if it appears an odd number of times. So, the number of such subsequences is:

Contribution count for bit b = (all combinations with odd count of 1s) * (all combinations of 0s)
= 2^(cnt1 - 1) * 2^cnt0
= 2^(cnt1 - 1 + cnt0)
= 2^(m - 1) [since cnt1 + cnt0 = m]

Now, multiplying by the bit's value 2^b gives the total contribution from bit b:

Contribution from bit b = 2^(m - 1) * 2^b

To handle dynamic updates (using XOR) and answer range queries efficiently, we store and update the current values directly using the bitwise OR of a given segment.

For a query on the range [l, r], we compute the bitwise OR of all elements in that range. The intuition is that if a particular bit appears in any element of the range, it will contribute to the final result.

Now, since each subsequence in the range can include or exclude elements (except the empty one), there are non-empty subsequences in total. In every such subsequence, the presence of that bit contributes the same value if it appears in the OR of the segment.

Hence, the final answer is:

Result = OR of the range * 2^(r - 1) mod 10^9 + 7

Code:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 3, mod = 1e9 + 7;
int arr[N];

struct Segment_Tree {
    int t[4 * N];

    auto merge(auto &l, auto &r) {
        return l | r;
    }
    void build(int node, int st, int en) { 
        if (st == en) {
            t[node] = arr[st];
            return;
        }
        int mid = (st + en) >> 1;
        build(node << 1, st, mid); 
        build(node << 1 | 1, mid + 1, en); 
        auto &Cur = t[node];
        auto &Left = t[node << 1];
        auto &Right = t[node << 1 | 1];
        Cur = merge(Left, Right);
        return;
    }
    void update(int node, int st, int en, int idx, int val) { 
        if (st == en) {
            t[node] = val;
            return;
        }
        int mid = (st + en) >> 1;
        if (idx <= mid) update(node << 1, st, mid, idx, val);
        else update(node << 1 | 1, mid + 1, en, idx, val);
        auto &Cur = t[node];
        auto &Left = t[node << 1];
        auto &Right = t[node << 1 | 1];
        Cur = merge(Left, Right);
        return;
    }
    int query(int node, int st, int en, int l, int r) { 
        if (st > r || en < l) { 
            return 0; 
        }
        if (l <= st && en <= r) { 
            return t[node];
        }
        int mid = (st + en) >> 1;
        auto Left = query(node << 1, st, mid, l, r);
        auto Right = query(node << 1 | 1, mid + 1, en, l, r);
        return merge(Left, Right);
    }
} st1;

ll Pow(ll a, ll b) {
    ll ans = 1 % mod;
    a %= mod;
    if(a < 0) a += mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    st1.build(1, 1, n);
    while(q--) {
        int type; 
        cin >> type;
        if(type == 1) {
            int pos, x;
            cin >> pos >> x;
            arr[pos] ^= x;
            st1.update(1, 1, n, pos, arr[pos]);
        }
        else {
            int l, r, sum = 0;
            cin >> l >> r;
            bitset<20> orr = st1.query(1, 1, n, l, r);
            for(int b = 0; b < 20; b++) {
                if(orr[b]) {
                    sum += (1 << b);
                    sum %= mod;
                }
            }
            sum = (sum * Pow(2, r - l)) % mod;
            if(sum < 0) sum += mod;
            cout << sum << '\n';
        }
    }
    return 0;
}