@@ -77,3 +77,56 @@ setTree* right;
77772. bool setTracking(int a, int b, bool tracking)
78783. bool setTracking(int a, int b)
7979```
80+ ``` cpp
81+ void remove (SegTree* &node)
82+ {
83+ if (!node) return;
84+ remove(node->left);
85+ remove(node->right);
86+ delete node;
87+ node = NULL;
88+ }
89+
90+ bool setTracking(int a, int b, bool tracking)
91+ {
92+ if (a<=begin && end<=b) //如果该区间被包括在了[ a,b] 内,则整体标记
93+ {
94+ remove(left);
95+ remove(right);
96+ return tracked = tracking;
97+ }
98+ int mid = (end-begin)/2+begin; //如果该区间和[ a,b] 只是部分相交,则需要往下搜索
99+ if (!left) //如果没有子区间,则需要立即创建.注意子区间的tracked可以完全继承自该区间的tracked
100+ {
101+ left = new SegTree(begin,mid,tracked);
102+ right = new SegTree(mid,end,tracked);
103+ }
104+ bool leftTracked, rightTracked;
105+ if (a<mid)
106+ leftTracked = left->setTracking(a,b,tracking);
107+ else
108+ leftTracked = left->tracked;
109+ if (b>mid)
110+ rightTracked = right->setTracking(a,b,tracking);
111+ else
112+ rightTracked = right->tracked;
113+ return tracked = leftTracked && rightTracked; // 父区间的tracked,永远来自两个子区间tracked的"与"
114+ }
115+
116+ bool getTracking(int a, int b)
117+ {
118+ if (!left && !right) return tracked;
119+ if (a<=begin && end<=b) return tracked;
120+ int mid = (end-begin)/2+begin;
121+ bool leftTracked, rightTracked;
122+ if (a<mid)
123+ leftTracked = left->getTracking(a,b);
124+ else
125+ leftTracked = true;
126+ if (b>mid)
127+ rightTracked = right->getTracking(a,b);
128+ else
129+ rightTracked = true;
130+ return leftTracked && rightTracked;
131+ }
132+ ```
0 commit comments