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?↵
↵
↵
↵
↵
↵
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?↵
↵
↵
↵
