### coder333's blog

By coder333, history, 4 weeks ago,

I’m trying to solve HackersEarth/CodeMonks problem called Bit operations. Unfortunately, I can't share the link of the problem (it is unshareable, you only can unlock the next section link by solving previously given problems).

Here is the problem:

You are given an array of size n. Initially, all the elements of the array are zero. You are given q queries, where each query is of the following type:

• 1 LRX: For each element in the range [L,R] like y, set y=y|X
• 2 LRX: For each element in the range [L,R] like y, set y=y&X
• 3 LRX: For each element in the range [L,R] like y, set y=y⊕X
• 4 LR: Print the sum of the elements in the range [L,R]
• 5 LR: Print the result after performing the XOR operation of the elements in the range [L,R]

I have tried to solve this problem via BIt and segment tree and in case of both I'm getting TLE and I got stuck on this problem.

Here is my approach using bit:

#include <iostream>
#include <vector>
using namespace std;

void update_sum(vector<int>& bit, const int idx, const int val) {
for(int i = idx; i < bit.size(); i += i & (-i)) {
bit[i] += val;
}
}

int query_sum(vector<int>& bit, int idx) {
int sum = 0;
while(idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
}

int query_element(vector<int>& bit, int idx) {
int sum = bit[idx];
if (idx > 0) {
int z = idx - (idx & -idx);
idx--;
while (idx != z) {
sum -= bit[idx];
idx -= (idx & -idx);
}
}
return sum;
}

int query_range_sum(vector<int>& bit, int left, int right) {
int left_sum = query_sum(bit, left - 1);
int right_sum = query_sum(bit, right);
return right_sum - left_sum;
}

int query_xor(vector<int>& bit, int l, int r) {
int s = r;
int _xor = query_element(bit, s);
--r;
while(r >= l) {
s = r;
_xor ^= query_element(bit, s);
--r;
}
return _xor;
}

void _xor(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] ^= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}

void _or(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] |= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}

void _and(vector<int>& bit, vector<int>& arr, const int val, const int l, const int r) {
for(int i = l - 1; i < r; ++i) {
int temp = arr[i];
arr[i] &= val;
update_sum(bit, i + 1, arr[i] - temp);
}
}

int main() {
int n = 0;
cin >> n;
int q = 0;
cin >> q;
vector<int> arr(n, 0);
vector<int> bit(n + 1, 0);
while(q--) {
int type = 0;
cin >> type;
if(type == 5) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query_xor(bit, l, r);
cout << ans << "\n";
} else if(type == 4) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query_range_sum(bit, l, r);
cout << ans << "\n";
} else if(type == 1) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_or(bit, arr, val, l, r);
} else if(type == 2) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_and(bit, arr, val, l, r);
} else if(type == 3) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
_xor(bit, arr, val, l, r);
}
}
return 0;
}

And here is my approach using Segment tree:

#include <iostream>
#include <vector>

using namespace std;

#define MAX_SIZE 200000

int tree[4 * MAX_SIZE];

void update_xor(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] ^= val;
} else {
int m = start + (end - start) / 2;
update_xor(2 * v, val, start, m, l, r);
update_xor(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}

void update_and(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] &= val;
return;
} else {
int m = start + (end - start) / 2;
update_and(2 * v, val, start, m, l, r);
update_and(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}

void update_or(int v, int val, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
tree[v] |= val;
return;
} else {
int m = start + (end - start) / 2;
update_or(2 * v, val, start, m, l, r);
update_or(2 * v + 1, val, m + 1, end, l, r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}

int query(int v, int start, int end, int l, int r) {
if(l > r) {
return 0;
}
if(start == l && end == r) {
return tree[v];
}
int m = start + (end - start) / 2;
return query(2 * v, start, m, l, min(r, m)) + query(2 * v + 1, m + 1, end, max(m + 1, l), r);
}

void query_xor(int v, int& _xor, int start, int end, int l, int r) {
if(end < l || start > r || start > end) {
return;
}
if(start == end) {
_xor ^= tree[v];
return;
} else {
int m = start + (end - start) / 2;
query_xor(2 * v, _xor, start, m, l, r);
query_xor(2 * v + 1, _xor, m + 1, end, l, r);
}
}

int main() {
int n = 0;
cin >> n;
int q = 0;
cin >> q;
while(q--) {
int type = 0;
cin >> type;
if(type == 5) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int _xor = 0;
query_xor(1, _xor, 1, n, l, r);
cout << _xor << "\n";
} else if(type == 4) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int ans = query(1, 1, n, l, r);
cout << ans << "\n";
} else if(type == 1) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_or(1, val, 1, n, l, r);
} else if(type == 2) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_and(1, val, 1, n, l, r);
} else if(type == 3) {
int l = 0;
cin >> l;
int r = 0;
cin >> r;
int val = 0;
cin >> val;
update_xor(1, val, 1, n, l, r);
}
}
return 0;
}

Currently, I'm trying to optimize the segment tree-based solution by applying lazy propagation, but I couldn't find a way to use it because in the case of sum segment tree, we can use lazy propagation to calculate the parent node sum value just in this way:

void updateRange(int node, int start, int end, int l, int r, int val)
{
if(lazy[node] != 0)
{
tree[node] += (end - start + 1) * lazy[node];
if(start != end)
{
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
if(start > end or start > r or end < l)
return;
if(start >= l and end <= r)
{
tree[node] += (end - start + 1) * val;
if(start != end)
{
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val);
updateRange(node*2 + 1, mid + 1, end, l, r, val);
tree[node] = tree[node*2] + tree[node*2+1];
}

But the problem in the case of XOR, ANd OR is that we can’t write something like (end — start + 1) * val for the i-th parent node.

Could you please give me some hints?

• +6

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by coder333 (previous revision, new revision, compare).
 » 4 weeks ago, # | ← Rev. 3 →   +17 HintConsider each bit separately. Can you find the contribution of each bit independently? SolutionConsider each bit separately. Consider only what happens to the $i$th bit after an OR operation on a range $[l, r]$. If $i$th bit of $x$ is $0$, noting changes, if it is $1$, all numbers in the range has bit $1$ afterwards. So, the operation becomes a range assignment operation. Similar simplifications can be applied for AND and XOR ops. For answering queries, we only need to know the number of 1s in a range. So we may keep a segment tree for each bit.Similar problem: https://www.spoj.com/problems/SUMSUM/en/
•  » » 4 weeks ago, # ^ |   0 Thank you very much.