fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. #define left(i) (2*i + 1)
  5. #define right(i) (2*i + 2)
  6. #define parent(i) ((i-1)/2)
  7. #include <vector>
  8.  
  9. template<class T>
  10. class SegmentTree
  11. {
  12.     public:
  13.         SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  14.         SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  15.         T query(int l, int r);
  16.         void update(int idx, T val);
  17.         //TODO lazy propagation
  18.     private:
  19.         T *tree;
  20.         void buildTree(std::vector<T> data);
  21.         int segTreeSize;
  22.         T valueForExtraNodes;
  23.         T (*combine)(T obj1, T obj2);
  24.         int calculateSize(int n);
  25.         T queryHelper(int l,int r, int st, int ed, int node);
  26. };
  27.  
  28. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  29.                                                 T value, T (*combine)(T obj1, T obj2))
  30. {
  31.    this->combine = combine;
  32.    valueForExtraNodes = value;
  33.    segTreeSize = calculateSize(data.size());
  34.    buildTree(data);
  35. }
  36.  
  37. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  38.                                             T value, T (*combine)(T obj1, T obj2))
  39. {
  40.    this->combine = combine;
  41.    valueForExtraNodes = value;
  42.    segTreeSize = calculateSize(n);
  43.  
  44.    std::vector<T> data;
  45.    for(int i = 0; i < n; i++)
  46.          data.push_back(ar[i]);
  47.  
  48.    buildTree(data);
  49. }
  50.  
  51.  
  52. template<class T> int SegmentTree<T>::calculateSize(int n)
  53. {
  54.     int pow2 = 1;
  55.     while( pow2 < n)
  56.     {
  57.         pow2 = pow2 << 1;
  58.     }
  59.     return 2*pow2 - 1;
  60. }
  61.  
  62. template<class T> T SegmentTree<T>::query(int l, int r)
  63. {
  64.     int st = 0, ed = segTreeSize/2;
  65.     return queryHelper(l, r, st, ed, 0);
  66. }
  67.  
  68. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  69. {
  70.     if( (r < st) || (l > ed) || (l > r) )
  71.         return valueForExtraNodes;
  72.     if(st >= l && ed <= r)
  73.         return tree[node];
  74.     T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  75.     T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  76.     return combine(leftVal, rightVal);
  77. }
  78.  
  79. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  80. {
  81.    int n = data.size();
  82.    tree = new T[segTreeSize];
  83.    int extraNodes = (segTreeSize/2 + 1) - n;
  84.    for(int i = segTreeSize - 1; i >= 0; i--)
  85.    {
  86.        if(extraNodes>0)
  87.            {
  88.                tree[i] = valueForExtraNodes;
  89.                extraNodes--;
  90.            }
  91.        else if(n>0)
  92.            {
  93.                tree[i] = data[n-1];
  94.                n--;
  95.            }
  96.        else
  97.            tree[i] = combine(tree[left(i)], tree[right(i)]);
  98.    }
  99. }
  100.  
  101. template<class T> void SegmentTree<T>::update(int idx, T val)
  102. {
  103.     int segTreeIdx = (segTreeSize/2) + idx;
  104.     tree[segTreeIdx] = val;
  105.     while(parent(segTreeIdx) >= 0)
  106.     {
  107.         segTreeIdx = parent(segTreeIdx);
  108.         if(right(segTreeIdx) < segTreeSize)
  109.           tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  110.         if(segTreeIdx == 0)
  111.             break;
  112.     }
  113. }
  114.  
  115. int xor_sum(int x,int y) { return x^y; }
  116. int main()
  117. {
  118.     int n,q;
  119.     cin>>n>>q;
  120.     vector<int> v(n);
  121.     for(int i=0;i<n;i++)
  122.         cin >> v[i];
  123.     SegmentTree<int> xorSumQueries(v, 0, xor_sum);
  124.     while(q--)
  125.     {
  126.         int l,r;
  127.         cin >> l >> r;
  128.         cout<<xorSumQueries.query(l-1,r-1)<<'\n';
  129.     }
  130.     return 0;
  131. }
  132.  
  133.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
stdout
copy 
3
0
6
4
https://ideone.com/mPhqas
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!