Consider the following problem:

You are given an array arr of size ( N ). Initially, all arr[i] are set to 0. You have Q queries, each falling into one of the following two types:

1. Type 1 query [1, l, r]: Calculate the sum of values of arr[i] for ( l \leq i \leq r ).
2. Type 2 query [2, l, r, x]: Update each arr[i] for ( l \leq i \leq r ) as arr[i] = arr[i] ^ x (where ( ^ ) denotes the XOR operation).

Constraints: - ( 1 \leq N, Q \leq 10^5 ) - ( 1 \leq l \leq r \leq N ) - ( 1 \leq x \leq 2^{30} — 1 )

Approach:

This problem can be efficiently solved using a Segment Tree with Lazy Propagation, especially due to the XOR updates which complicate direct updates but are manageable with the right data structure.

Segment Tree with Lazy Propagation:

Segment Trees with Lazy Propagation are ideal for handling range queries and updates efficiently. However, XOR updates require special handling. Let's break down the solution approach:

1. Handling Type 1 Queries:

• For sum queries, the segment tree can maintain arrays for each bit position (from 0 to 29 for numbers up to ( 2^{30} — 1 )).
• Each array tracks counts of set bits (1s) in the corresponding bit position across the array arr.
• The sum over range [l, r] can then be computed using these arrays.

1. Handling Type 2 Queries:

• XOR updates toggle bits based on the bits set in x.
• To efficiently apply these updates across the segment tree, toggle the relevant bit arrays corresponding to the bits set in x for the range [l, r].

Implementation Details:

• Initialize 30 bit arrays to track counts of set bits across the range of arr.
• Use a segment tree to manage these bit arrays efficiently for both queries and updates.
• For each Type 1 query, compute the sum using precomputed bit arrays.
• For each Type 2 query, update the segment tree by toggling the relevant bit arrays based on the bits set in x.

This approach ensures that both query types are handled in ( O(\log N) ) time due to the efficient range operations of the segment tree, making it suitable for large input sizes up to ( 10^5 ).

By leveraging Segment Trees with Lazy Propagation and specialized handling of XOR updates, we can efficiently solve the problem even with the constraints provided.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
struct LazySegmentTree {
  int n;
  vector<ll> L, R;
  vector<int> val;
  vector<bool> lazy;

  LazySegmentTree(int sz) {
    n = 4 * sz;
    L.resize(n);
    R.resize(n);
    lazy.resize(n);
    val.resize(n);
    n >>= 1;
    init(1, 0, sz - 1);
  }

  void init(int node, int l, int r) {
    if (l > r) {
      return;
    }
    L[node] = l;
    R[node] = r;
    if (l < r) {
      int mid = (l + r) / 2;
      init(2 * node, l, mid);
      init(2 * node + 1, mid + 1, r);
    }
  }

  void flip(int node){
    lazy[node] = lazy[node] ^ 1;
    val[node] = (R[node] - L[node] + 1) - val[node]; // Updating sum for range
  }

  void propagate(int node) {
    if(L[node] < R[node]){
      if(lazy[node]){
        flip(2 * node);
        flip(2 * node + 1);
        lazy[node] = 0;
      }
    }
  }

  void set(int node, int l, int r) {
    if (r < L[node] || R[node] < l) {
      return;
    }
    if (l <= L[node] && R[node] <= r) {
      flip(node);
    } else {
      propagate(node);
      set(2 * node, l, r);
      set(2 * node + 1, l, r);
      val[node] = val[2 * node] + val[2 * node + 1];
    }
  }

  ll get(int node, int l, int r) {
    if (r < L[node] || R[node] < l) {
      return 0; // Out of range
    }
    if (l <= L[node] && R[node] <= r) {
      return val[node];
    }
    propagate(node);
    ll left_sum = get(2 * node, l, r);
    ll right_sum = get(2 * node + 1, l, r);
    return left_sum + right_sum;
  }
};

const int LOGMAX = 30;
 
vector<ll> solve(int n, vector<vector<int>> &queries) {
  vector<LazySegmentTree> tree;
  for(int k = 0; k < LOGMAX; ++k){
    tree.push_back(LazySegmentTree(n + 1));
  }
  vector<ll> res;
  for(vector<int> &query: queries){
    int type = query[0];
    if(type == 1){
      int l = query[1];
      int r = query[2];
      ll sum = 0;
      for(int k = 0; k < LOGMAX; ++k){
        sum += (1ll << k) * tree[k].get(1, l, r);
      }
      res.push_back(sum);
    }
    else{
      int l = query[1];
      int r = query[2];
      int x = query[3];
      for(int k = 0; k < LOGMAX; ++k){
        if(1 & (x >> k)){
          tree[k].set(1, l, r);
        }
      }
    }
  }
  return res;
}

vector<ll> brute(int n, vector<vector<int>> &queries) {
  vector<int> arr(n + 1);
  vector<ll> res;
  for(vector<int> &query: queries){
    int type = query[0];
    if(type == 1){
      int l = query[1];
      int r = query[2];
      ll sum = 0;
      for(int i = l; i <= r; ++i){
        sum += arr[i];
      }
      res.push_back(sum);
    }
    else{
      int l = query[1];
      int r = query[2];
      int x = query[3];
      for(int i = l; i <= r; ++i){
        arr[i] = arr[i] ^ x;
      }
    }
  }
  return res;
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n, q;
  cin >> n >> q;
  vector<vector<int>> queries(q);
  for(int i = 0; i < q; ++i){
    int type, l, r;
    cin >> type >> l >> r;
    queries[i] = {type, l, r};
    if(type == 2){
      int x;
      cin >> x;
      queries[i].push_back(x);
    }
  }

  for(ll elem: brute(n, queries)){
    cout << elem << '\n';
  }

  assert(solve(n, queries) == brute(n, queries));

  
  return 0;
}