Xor sum

#include <iostream>
#include <utility>
#include <vector>


struct SegmentTree{
  std::vector<int> tree;
  int size;
  SegmentTree(std::vector<int>& arr){
    size = arr.size();
    tree.resize(4*size);
    buildTree(0, 0, size-1, arr);
  }

  void buildTree(int treeIndex, int rangeL, int rangeR, std::vector<int>& arr){
    if (rangeL==rangeR){
      tree[treeIndex] = arr[rangeL];
      return;
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);
    buildTree(treeLeftIdx, rangeL, mid, arr);
    buildTree(treeRightIdx, mid+1, rangeR, arr);

    tree[treeIndex] = tree[treeLeftIdx]^tree[treeRightIdx];
  }

  int getLeft(int idx){
    return 2*idx+1;
  }

  int getRight(int idx){
    return 2*idx+2;
  }
  
  int query(int treeIndex, int ql, int qr, int rangeL, int rangeR){
    if (ql <= rangeL && qr >= rangeR){
      return tree[treeIndex];
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);

    int sum = 0;

    if (ql<=mid){
      sum^= query(treeLeftIdx, ql, qr, rangeL, mid);
    }
    if (qr>mid){
      sum^= query(treeRightIdx, ql, qr, mid+1, rangeR);
    }

    return sum;
  }
};



int main(){
  int n, m;
  std::cin >> n >> m;
  std::vector<int> vals(n);
  for (int i = 0; i<n; ++i){
    std::cin >> vals[i];
  }
  SegmentTree st(vals);
  
  std::vector<std::pair<int, int>> queries(m);
  for (int q = 0; q<m; ++q){
    int ql,qr;
    std::cin >> ql >> qr;
    queries[q].first = ql-1;
    queries[q].second = qr-1;
  }

  for (int q = 0; q<m; ++q){
    int sum = st.query(0, queries[q].first, queries[q].second, 0, st.size-1);
    std::cout << sum << "\n";
  }


}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED