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 root->value = val;

14 root->left = root->right = NULL; // memory leak;

15 return;

16 }

17

18 const int mid = root->low + (root->high - root->low) / 2;

19

20 if (!root->left) {

21 root->left = new Node(root->low, mid, root->value);

22 root->right = new Node(mid + 1, root->high, root->value);

23 }

24

25 if (r <= mid)

26 update(root->left, l, r, val);

27 else if (l > mid)

28 update(root->right, l, r, val);

29 else

30 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)

41 return query(root->left, l, r);

42 else if (l > mid)

43 return query(root->right, l, r);

44 return query(root->left, l, mid) && query(root->right, mid + 1, r);

45 }

46

47 public:

48 SegmentTree(int l, int r, int val) : root(l, r, val) {}

49

50 void update(int l, int r, int val) { return update(&root, l, r, val); }

51 bool query(int l, int r) const { return query(&root, l, r); }

52 };

53

54 class RangeModule {

55 SegmentTree seg;

56

57 public:

58 RangeModule() : seg(0, 1e9, 0) {}

59

60 void addRange(int left, int right) { seg.update(left, right - 1, 1); }

61

62 bool queryRange(int left, int right) { return seg.query(left, right - 1); }

63

64 void removeRange(int left, int right) { seg.update(left, right - 1, 0); }

65 };