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?