区间赋值状态压缩线段树

有一次打比赛见到的，求一段区间内所有值的异或，对整块区间进行赋值，当时比赛时没有将模板调出来，感觉状压线段树可以当模板整理下来，转载注明出处谢谢

 1 /*
 2 _sum是对区间所有元素做或云算的值
 3 */
 4 int _sum, y11, y22, v;
 5 struct IntervalTree {
 6     int sumv[maxnode], setv[maxnode];
 7 
 8     // 维护信息
 9     void maintain(int o, int L, int R) {
10         int lc = o*2, rc = o*2+1;
11         if(R > L) sumv[o] = sumv[lc] | sumv[rc];
12         if(setv[o] >= 0) sumv[o] = setv[o];
13     }
14 
15     // 标记传递
16     void unmark(int o) {
17         int lc = o*2, rc = o*2+1;
18         if(setv[o] >= 0) {
19             setv[lc] = setv[rc] = setv[o];
20             setv[o] = -1; // 清除本结点标记
21         }
22     }
23     void update(int o, int L, int R) {
24         int lc = o*2, rc = o*2+1;
25         if(y11 <= L && y22 >= R) setv[o] = v;
26         else 
27         {
28             unmark(o);
29             int M = L + (R-L)/2;
30             if(y11 <= M) update(lc, L, M); else maintain(lc, L, M);
31             if(y22 > M) update(rc, M+1, R); else maintain(rc, M+1, R);
32         }
33         maintain(o, L, R);
34     }
35     void query(int o, int L, int R) {
36         if(setv[o] >= 0) _sum |= setv[o];
37         else if(y11 <= L && y22 >= R) _sum |= sumv[o];
38         else {
39             int M = L + (R-L)/2;
40             if(y11 <= M) query(o*2, L, M);
41             if(y22 > M) query(o*2+1, M+1, R);
42         }
43     }
44 } tree;

区间赋值状态压缩线段树

推荐阅读