leetcode715 Range模块

思路：

动态开点线段树，这里维护了区间赋值和区间和。

实现：

 1 class SegmentTree {
 2 public:
 3     int N = (int)1e9;
 4     class Node {
 5     public:
 6         // ls 和 rs 分别代表当前区间的左右子节点
 7         Node*ls=nullptr, *rs=nullptr;
 8         // val 代表当前区间的最大高度，add 为懒标记
 9         int val=0, add=-1;//add需要是赋值操作中未出现的值
10         Node(){}
11     };
12     vectornodes_pool;
13     Node*root = nullptr;
14     int cur_id=0;
15     SegmentTree(int n,int num_nodes){
16         N=n;
17         nodes_pool.resize(num_nodes);
18         root=&nodes_pool[cur_id++];
19     }
20     void update(int l,int r,int v){
21         _update(root,0,N,l,r,v);
22     }
23     void _update(Node*node, int lc, int rc, int l, int r, int v) {
24         if (l <= lc && rc <= r) {
25             node->add = v;
26             node->val = v*(rc-lc+1);
27             return ;
28         }
29         pushdown(node,lc,rc);
30         int mid = lc + rc >> 1;
31         if (l <= mid) _update(node->ls, lc, mid, l, r, v);
32         if (r > mid) _update(node->rs, mid + 1, rc, l, r, v);
33         pushup(node);
34     }
35     int query(int l,int r){
36         return _query(root,0,N,l,r);
37     }
38     int _query(Node*node, int lc, int rc, int l, int r) {
39         if (l <= lc && rc <= r) return node->val;
40         pushdown(node,lc,rc);
41         int mid = lc + rc >> 1, ans = 0;
42         if (l <= mid) ans = _query(node->ls, lc, mid, l, r);
43         if (r > mid) ans += _query(node->rs, mid + 1, rc, l, r);
44         return ans;
45     }
46     void pushdown(Node*node,int lc,int rc) {
47         if (node->ls == nullptr) node->ls = &nodes_pool[cur_id++];
48         if (node->rs == nullptr) node->rs = &nodes_pool[cur_id++];
49         if (node->add == -1) return ;//node->add初始值应为赋值操作中未出现的值，否则这里会混淆
50         int mid=lc+rc>>1;
51         node->ls->add = node->add; node->rs->add = node->add;
52         node->ls->val = node->add*(mid-lc+1); node->rs->val = node->add*(rc-mid);
53         node->add = -1;
54     }
55     void pushup(Node*node) {
56         node->val = node->ls->val + node->rs->val;
57     }
58 
59 };
60 class RangeModule {
61 public:
62     SegmentTree*st=NULL;
63     RangeModule() {
64         st=new SegmentTree(1e9,500000);
65     }
66     
67     void addRange(int left, int right) {
68         st->update(left,right-1,1);
69     }
70     
71     bool queryRange(int left, int right) {
72         int sum=st->query(left,right-1);
73         return sum==right-left;
74     }
75     
76     void removeRange(int left, int right) {
77         st->update(left,right-1,0);
78     }
79 };
80 
81 /**
82  * Your RangeModule object will be instantiated and called as such:
83  * RangeModule* obj = new RangeModule();
84  * obj->addRange(left,right);
85  */