leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

segment_tree_dynamic_recursive.cpp (1631B)

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