leetcode

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 };