### Problem Statement:↵
↵
You are given an array `arr` of size $N$. Initially, all $arr[i]$ are set to 0. Now consider $Q$ queries, where each query is of one of the following two types:↵
↵
1. **\[1, l, r\]:** In this case, calculate the sum of values of $arr[i]$ for $l \le i \le r$.↵
2. **\[2, l, r, x\]:** In this case, for each $arr[i]$, $l \le i \le r$, update the value to $arr[i] = arr[i] \oplus x$ (where $\oplus$ is the XOR operation).↵
↵
### Constraints:↵
1. $ 1 \le N \le 10^5 $↵
2. $ 1 \le Q \le 10^5 $↵
3. $ 1 \le l \le r \le N $↵
4. $ 1 \le x \le 2^{30} - 1 $↵
↵
Problem Link — [problem:242E]↵
↵
---↵
↵
### Approach:↵
↵
This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range $[l, r]$, we should be able to calculate the value of $[l, r]$ after the update in $O(1)$ time (or at least sub-linear time like $O(\log n)$).↵
↵
For other updates, say multiply by $x$, this would be simple. The value of $[l, r]$ after the update would be:↵
↵
new_sum = x * prev_sum↵
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
<spoiler summary="Simplifying the XOR Update">↵
### Simplifying the XOR Update:↵
↵
Consider a simpler problem. Let's say that all values in `arr` can be either 0 or 1, and even $x$ can be only 0 or 1.↵
↵
Now the sum of range $[l, r]$ is $S$, which indicates that there are $S$ 1s and $r — l + 1 — S$ 0s in $[l, r]$.↵
↵
1. An update with $x = 0$ won’t change anything.↵
2. An update with $x = 1$ would flip 0s and 1s, so there will be $r - l + 1 - S $ 1s and $S$ 0s. The new sum is:↵
↵
↵
$r - l + 1 - S $↵
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Generalizing for the Full Problem:">↵
### Generalizing for the Full Problem:↵
↵
The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.↵
↵
So, we build $LOGMAX (=30)$ such arrays, and for each query:↵
↵
1. For sum $[l, r]$, calculate ${sum}_0, \text{sum}_1, \ldots, \text{sum}_{29}$ for each of the trees. The final sum is:↵
↵
↵
$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}$↵
↵
2. For the update $[l, r]$ with XOR $x$, flip $[l, r]$ for the $k^{th}$ tree if the $k^{th}$ bit of $x$ is set.↵
</spoiler>↵
↵
--- ↵
↵
<spoiler summary="Code">↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
struct LazySegmentTree {↵
const int LOGMAX = 30;↵
int n;↵
vector<int> lazy;↵
vector<vector<int>> sum;↵
vector<int> L, R;↵
↵
LazySegmentTree(vector<int>& arr) {↵
int sz = arr.size();↵
n = 1;↵
while (n < sz) n <<= 1;↵
lazy.assign(2 * n, 0);↵
sum.assign(2 * n, vector<int>(LOGMAX, 0));↵
L.assign(2 * n, 0);↵
R.assign(2 * n, 0);↵
↵
↵
// Initialize the segment tree leaves↵
for (int i = 0; i < sz; ++i) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[i + n][k] = (arr[i] >> k) & 1;↵
}↵
}↵
for(int i = 0; i < n; ++i){↵
L[i + n] = R[i + n] = i;↵
}↵
↵
// Build the segment tree↵
for (int i = n - 1; i > 0; --i) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[i][k] = sum[2 * i][k] + sum[2 * i + 1][k];↵
}↵
L[i] = L[2 * i];↵
R[i] = R[2 * i + 1];↵
}↵
}↵
↵
void apply(int node, int x) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
if (x & (1 << k)) {↵
sum[node][k] = (R[node] - L[node] + 1) - sum[node][k];↵
}↵
}↵
if (node < n) {↵
lazy[node] ^= x;↵
}↵
}↵
↵
void propagate(int node) {↵
if (lazy[node]) {↵
apply(2 * node, lazy[node]);↵
apply(2 * node + 1, lazy[node]);↵
lazy[node] = 0;↵
}↵
}↵
↵
void update(int node) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[node][k] = sum[2 * node][k] + sum[2 * node + 1][k];↵
}↵
}↵
↵
void rangeUpdate(int l, int r, int x) {↵
l += n;↵
r += n;↵
int l0 = l, r0 = r;↵
↵
// Apply any existing lazy updates↵
for (int i = __lg(n); i >= 1; --i) {↵
if ((l >> i) > 0) propagate(l >> i);↵
if ((r >> i) > 0) propagate(r >> i);↵
}↵
↵
// Update the segment tree↵
for (; l <= r; l >>= 1, r >>= 1) {↵
if (l & 1) apply(l++, x);↵
if (!(r & 1)) apply(r--, x);↵
}↵
↵
// Update affected parent nodes↵
for (l = l0 >> 1; l > 0; l >>= 1) propagate(l), update(l);↵
for (r = r0 >> 1; r > 0; r >>= 1) propagate(r), update(r);↵
}↵
↵
↵
long long rangeQuery(int l, int r) {↵
l += n;↵
r += n;↵
long long res = 0;↵
↵
// Apply any existing lazy updates↵
for (int i = __lg(n); i >= 1; --i) {↵
if ((l >> i) > 0) propagate(l >> i);↵
if ((r >> i) > 0) propagate(r >> i);↵
}↵
↵
// Query the segment tree↵
for (; l <= r; l >>= 1, r >>= 1) {↵
if (l & 1) res += getSum(l++);↵
if (!(r & 1)) res += getSum(r--);↵
}↵
↵
return res;↵
}↵
↵
long long getSum(int node) {↵
long long result = 0;↵
for (int k = 0; k < LOGMAX; ++k) {↵
result += (1LL << k) * sum[node][k];↵
}↵
return result;↵
}↵
};↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for(int i = 1; i <= n; ++i){↵
cin >> a[i];↵
}↵
↵
LazySegmentTree tree(a);↵
↵
int q;↵
cin >> q;↵
while(q--){↵
int type, l, r;↵
cin >> type >> l >> r;↵
if(type == 1){↵
cout << tree.rangeQuery(l, r) << '\n';↵
}↵
else{↵
int x;↵
cin >> x;↵
tree.rangeUpdate(l, r, x);↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
You are given an array `arr` of size $N$. Initially, all $arr[i]$ are set to 0. Now consider $Q$ queries, where each query is of one of the following two types:↵
↵
1. **\[1, l, r\]:** In this case, calculate the sum of values of $arr[i]$ for $l \le i \le r$.↵
2. **\[2, l, r, x\]:** In this case, for each $arr[i]$, $l \le i \le r$, update the value to $arr[i] = arr[i] \oplus x$ (where $\oplus$ is the XOR operation).↵
↵
### Constraints:↵
1. $ 1 \le N \le 10^5 $↵
2. $ 1 \le Q \le 10^5 $↵
3. $ 1 \le l \le r \le N $↵
4. $ 1 \le x \le 2^{30} - 1 $↵
↵
Problem Link — [problem:242E]↵
↵
---↵
↵
### Approach:↵
↵
This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range $[l, r]$, we should be able to calculate the value of $[l, r]$ after the update in $O(1)$ time (or at least sub-linear time like $O(\log n)$).↵
↵
For other updates, say multiply by $x$, this would be simple. The value of $[l, r]$ after the update would be:↵
↵
new_sum = x * prev_sum↵
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
<spoiler summary="Simplifying the XOR Update">↵
### Simplifying the XOR Update:↵
↵
Consider a simpler problem. Let's say that all values in `arr` can be either 0 or 1, and even $x$ can be only 0 or 1.↵
↵
Now the sum of range $[l, r]$ is $S$, which indicates that there are $S$ 1s and $r — l + 1 — S$ 0s in $[l, r]$.↵
↵
1. An update with $x = 0$ won’t change anything.↵
2. An update with $x = 1$ would flip 0s and 1s, so there will be $r - l + 1 - S $ 1s and $S$ 0s. The new sum is:↵
↵
↵
$r - l + 1 - S $↵
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Generalizing for the Full Problem:">↵
### Generalizing for the Full Problem:↵
↵
The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.↵
↵
So, we build $LOGMAX (=30)$ such arrays, and for each query:↵
↵
1. For sum $[l, r]$, calculate ${sum}_0, \text{sum}_1, \ldots, \text{sum}_{29}$ for each of the trees. The final sum is:↵
↵
↵
$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}$↵
↵
2. For the update $[l, r]$ with XOR $x$, flip $[l, r]$ for the $k^{th}$ tree if the $k^{th}$ bit of $x$ is set.↵
</spoiler>↵
↵
--- ↵
↵
<spoiler summary="Code">↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
struct LazySegmentTree {↵
const int LOGMAX = 30;↵
int n;↵
vector<int> lazy;↵
vector<vector<int>> sum;↵
vector<int> L, R;↵
↵
LazySegmentTree(vector<int>& arr) {↵
int sz = arr.size();↵
n = 1;↵
while (n < sz) n <<= 1;↵
lazy.assign(2 * n, 0);↵
sum.assign(2 * n, vector<int>(LOGMAX, 0));↵
L.assign(2 * n, 0);↵
R.assign(2 * n, 0);↵
↵
↵
// Initialize the segment tree leaves↵
for (int i = 0; i < sz; ++i) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[i + n][k] = (arr[i] >> k) & 1;↵
}↵
}↵
for(int i = 0; i < n; ++i){↵
L[i + n] = R[i + n] = i;↵
}↵
↵
// Build the segment tree↵
for (int i = n - 1; i > 0; --i) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[i][k] = sum[2 * i][k] + sum[2 * i + 1][k];↵
}↵
L[i] = L[2 * i];↵
R[i] = R[2 * i + 1];↵
}↵
}↵
↵
void apply(int node, int x) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
if (x & (1 << k)) {↵
sum[node][k] = (R[node] - L[node] + 1) - sum[node][k];↵
}↵
}↵
if (node < n) {↵
lazy[node] ^= x;↵
}↵
}↵
↵
void propagate(int node) {↵
if (lazy[node]) {↵
apply(2 * node, lazy[node]);↵
apply(2 * node + 1, lazy[node]);↵
lazy[node] = 0;↵
}↵
}↵
↵
void update(int node) {↵
for (int k = 0; k < LOGMAX; ++k) {↵
sum[node][k] = sum[2 * node][k] + sum[2 * node + 1][k];↵
}↵
}↵
↵
void rangeUpdate(int l, int r, int x) {↵
l += n;↵
r += n;↵
int l0 = l, r0 = r;↵
↵
// Apply any existing lazy updates↵
for (int i = __lg(n); i >= 1; --i) {↵
if ((l >> i) > 0) propagate(l >> i);↵
if ((r >> i) > 0) propagate(r >> i);↵
}↵
↵
// Update the segment tree↵
for (; l <= r; l >>= 1, r >>= 1) {↵
if (l & 1) apply(l++, x);↵
if (!(r & 1)) apply(r--, x);↵
}↵
↵
// Update affected parent nodes↵
for (l = l0 >> 1; l > 0; l >>= 1) propagate(l), update(l);↵
for (r = r0 >> 1; r > 0; r >>= 1) propagate(r), update(r);↵
}↵
↵
↵
long long rangeQuery(int l, int r) {↵
l += n;↵
r += n;↵
long long res = 0;↵
↵
// Apply any existing lazy updates↵
for (int i = __lg(n); i >= 1; --i) {↵
if ((l >> i) > 0) propagate(l >> i);↵
if ((r >> i) > 0) propagate(r >> i);↵
}↵
↵
// Query the segment tree↵
for (; l <= r; l >>= 1, r >>= 1) {↵
if (l & 1) res += getSum(l++);↵
if (!(r & 1)) res += getSum(r--);↵
}↵
↵
return res;↵
}↵
↵
long long getSum(int node) {↵
long long result = 0;↵
for (int k = 0; k < LOGMAX; ++k) {↵
result += (1LL << k) * sum[node][k];↵
}↵
return result;↵
}↵
};↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for(int i = 1; i <= n; ++i){↵
cin >> a[i];↵
}↵
↵
LazySegmentTree tree(a);↵
↵
int q;↵
cin >> q;↵
while(q--){↵
int type, l, r;↵
cin >> type >> l >> r;↵
if(type == 1){↵
cout << tree.rangeQuery(l, r) << '\n';↵
}↵
else{↵
int x;↵
cin >> x;↵
tree.rangeUpdate(l, r, x);↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
