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 :frowning:

error

Why ?

Uh, unfortunately, the link can’t be shared :frowning: 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 :slight_smile:

https://www.geeksforgeeks.org/xor-of-elements-in-a-given-range-with-updates-using-fenwick-tree/

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