leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

segment_tree_dynamic_recursive.cpp (1631B)

      1 class SegmentTree {
      2     struct Node {
      3         Node *left = nullptr;
      4         Node *right = nullptr;
      5         int low;
      6         int high;
      7         int value;
      8 
      9         Node (int low, int high, int value): low(low), high(high), value(value) {}
     10     } root;
     11 
     12     void update(Node *root, int l, int r, int val) {
     13         if(root->low == l && root->high == r)
     14         {
     15             root->value = val;
     16             root->left = root->right = NULL; // memory leak
     17             return;
     18         }
     19 
     20         const int mid = root->low + (root->high - root->low) / 2;
     21 
     22         if(!root->left)
     23         {
     24             root->left = new Node(root->low, mid, root->value);
     25             root->right = new Node(mid + 1, root->high, root->value);
     26         }
     27 
     28         if(r <= mid) update(root->left, l, r, val);
     29         else if(l > mid) update(root->right, l, r, val);
     30         else update(root->left, l, mid, val), update(root->right, mid + 1, r, val);
     31         root->value = root->left->value && root->right->value;
     32     }
     33 
     34     bool query(const Node *root, int l, int r) const {
     35         if(!root->left) return root->value;
     36         if(root->low == l && root->high == r)  return root->value;
     37 
     38         const int mid = root->low + (root->high - root->low) / 2;
     39 
     40         if(r <= mid) return query(root->left, l, r);
     41         else if(l > mid) return query(root->right, l, r);
     42         return query(root->left, l, mid) && query(root->right, mid + 1, r);
     43     }
     44 
     45 public:
     46     SegmentTree(int l, int r, int val): root(l, r, val) {}
     47 
     48     void update(int l, int r, int val) { return update(&root, l, r, val); }
     49     bool query(int l, int r) const { return query(&root, l, r); }
     50 };