@@ -87,46 +87,38 @@ setTree* right;
8787 node = NULL;
8888 }
8989
90- bool setTracking (int a, int b, bool tracking )
90+ int setStatus (int a, int b, int s )
9191 {
92- if (a<=begin && end<=b) //如果该区间被包括在了[ a,b] 内,则整体标记
92+ if (begin>=b || end<=a) // 1. [ a,b] 与这个区间不相交，返回原先的状态
93+ return status;
94+ if (a<=begin && end<=b) // 2. [ a,b] 包括了整个区间，将该区间抹平
9395 {
9496 remove(left);
9597 remove(right);
96- return tracked = tracking;
97- }
98- int mid = (end-begin)/2+begin; //如果该区间和[ a,b] 只是部分相交,则需要往下搜索
99- if (!left) //如果没有子区间,则需要立即创建.注意子区间的tracked可以完全继承自该区间的tracked
98+ return status = s;
99+ }
100+ if (!left) // 3. [ a,b] 与该区间相交，需考虑其子树
100101 {
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的"与"
102+ int mid = (end-begin)/2+begin;
103+ left = new SegTree(begin,mid,status);
104+ right = new SegTree(mid,end,status);
105+ }
106+ int leftStatus = left->setStatus(a,b,s);
107+ int rightStatus = right->setStatus(a,b,s);
108+ return status = leftStatus && rightStatus;
114109 }
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;
110+
111+ int getStatus(int a, int b)
112+ {
113+ if (begin>=b || end<=a) // 1. [ a,b] 与这个区间不相交，返回一个不影响结果的状态
114+ return true;
115+ if (a<=begin && end<=b) // 2. [ a,b] 包括了整个区间，返回该区间的状态
116+ return status;
117+ if (!left) // 3. [ a,b] 与该区间相交，但又没有子树，返回整个区间状态
118+ return status;
119+ int mid = (end-begin)/2+begin; // 4. [ a,b] 与该区间相交，需要考虑其子树
120+ int leftStatus = left->getStatus(a,b);
121+ int rightStatus = right->getStatus(a,b);
122+ return leftStatus && rightStatus;
131123 }
132124```
0 commit comments