# Getting TLE on the BIT while calculating the [L R] xor of elements

I’m trying to solve HackersEarth/CodeMonks problem called Bit operations. 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’ve used Binary Indexed tree as the problem marked under the "Tree"s category, and here is my code:

``````#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;
}
``````

But this code causes TLE on some test case. I suspect that the reason is the query_xor() function, but I can’t see some other way to get the XOR of the range [L, R] another way. Could you please help me with this TLE?

Regards.

Bro always share question link .

Uhhh, sorry. The link can’t be shared

error

Why ?

Uh, unfortunately, the link can’t be shared You have to reach at that point to activate it.

That’s how the HackerEarth’ CodeMonk works

share screenshot

Why I m not able to access code monk while u r allowed ?

I’m new In CodeCheef so it doesn’t allow me upload files but here is the link from the image hosting:

You have to solve the first few sections to reach to that point

which sections ?

Trees

https://www.hackerearth.com/practice/codemonk/v3/” here u go , now all users can access this. yeah I have to solve some problems first.

1 Like

Should I explain or better give u a link of the whole explanation ?

could you please give me the link, I would be thankful for that

Let me find more , wait.

1 Like

Or if it is comfortable for you can give a short explanation

as this is point update , I m thinking about range update too.

Thank you, I think following to this approach I need to construct the BIT every time before every AND, OR, XOR