SHARE
TWEET

Segment tree

keverman Jan 6th, 2019 147 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Segment tree (point-range)
  2. class stree
  3. {
  4.     private:
  5.        
  6.         std::vector<long long> data;
  7.         int height, size;
  8.        
  9.         long long queryRec(int a, int b, int n, int lhs, int rhs)
  10.         {
  11.             if(lhs >= a && rhs <= b) return data[n];
  12.  
  13.             int mid = ((lhs + rhs) >> 1);
  14.  
  15.             return ((mid < a ? 0 : queryRec(a, b, l(n), lhs, mid)) +
  16.                 (mid + 1 > b ? 0 : queryRec(a, b, r(n), mid + 1, rhs)));
  17.         }
  18.        
  19.     public:
  20.    
  21.         stree(int height)
  22.         {
  23.             this->height = height;
  24.             size = (1 << (height - 1));
  25.             data.resize(size * 2);
  26.         }
  27.        
  28.         void update(int pos, int val)
  29.         {
  30.             val -= data[(pos += size)];
  31.  
  32.             do{
  33.                 data[pos] += val;
  34.             }while((pos /= 2) > 0);
  35.         }
  36.        
  37.         long long query(int a, int b)
  38.         {
  39.             if(0 >= a && size - 1 <= b) return data[1];
  40.  
  41.             int mid = ((size - 1) >> 1);
  42.  
  43.             return ((mid < a ? 0 : queryRec(a, b, 2, 0, mid)) +
  44.                     (mid + 1 > b ? 0 : queryRec(a, b, 3, mid + 1, size - 1)));
  45.         }
  46.        
  47.         void visualize()
  48.         {
  49.             if(height < 7)
  50.             {
  51.                 for(int i = 0; i < height; i++)
  52.                 {
  53.                     for(int j = 0; j < ((1 << (height - i - 1)) - 1); j++) std::cout << " ";
  54.                    
  55.                     for(int j = 0; j < ((1 << i) - 1); j++)
  56.                     {
  57.                         std::cout << data[(1 << i) + j];
  58.                         for(int k = 0; k < ((1 << (height - i)) - 1); k++) std::cout << " ";
  59.                     }
  60.                    
  61.                     std::cout << data[(1 << (i + 1)) - 1];
  62.                     for(int j = 0; j < ((1 << (height - i - 1)) - 1); j++) std::cout << " ";
  63.                    
  64.                     std::cout << std::endl;
  65.                 }
  66.             }
  67.            
  68.             else
  69.             {
  70.                 std::cout << "The tree is too big to visualize!" << std::endl;
  71.             }
  72.         }
  73. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top