SGT 进阶（？

动态开点

当正常堆式建树开不下时（\(n\) 或 \(V\) 过大），通常使用动态开点。

例题

P2781 传教

算是很板了吧？

每次修改的时候，若当前访问节点未建立则新建节点并回溯至上一个节点记录左右儿子。实测写 & 引用或 struct 是很方便的。

要十分注意的是在 work 函数（单点修改 & 标记下放）里面一定要判断当前访问节点是否建立！

SGT namespace 代码：

namespace SGT {
	#define mid (L + R) >> 1
	#define son p, L, R
	#define lson ls[p], L, (L + R) >> 1
	#define rson rs[p], ((L + R) >> 1) + 1, R
	
	int tot, ls[N], rs[N], tag[N], sum[N];
	
	inline void psup(int p) {sum[p] = sum[ls[p]] + sum[rs[p]];}
	
	inline void work(int &p, int L, int R, int k) {
		if(!p) p = ++ tot;
		
		tag[p] += k;
		sum[p] += k * (R - L + 1);
	}
	
	inline void psd(int p, int L, int R) {
		work(lson, tag[p]), work(rson, tag[p]);
		
		tag[p] = 0;
	}
	
	inline void add(int l, int r, int k, int &p, int L = 1, int R = n)  {
		if(! p) p = ++ tot;
		
		if(l <= L && R <= r) {
			work(son, k);
			return;
		}
		
		psd(son);
		
		if(l <= mid) add(l, r, k, lson);
		if(r > mid) add(l, r, k, rson);
		
		psup(p);
	}
	
	inline int query(int l, int r, int &p, int L = 1, int R = n) {
		int res = 0;
		
		if(! p) return 0;
		
		if(l <= L && R <= r) return sum[p];
		
		psd(son);
		
		if(l <= mid) res += query(l, r, lson);
		if(r > mid) res += query(l, r, rson);
		
		return res;
	}
}