[可持久化权值线段树] [模板] [数组版本]

2021-06-09 15:03

阅读：587

标签：inline 持久化 max c++ str while for div 版本

[可持久化权值线段树] [模板] [数组版本]

\[1 \leq n \leq 2e5\|a_i| \leq 1e9 \]

感觉动态开点用指针好理解一点

但是太难调试了，还是数组版本吧

代码

int a[maxn],b[maxn],len;

inline int getid(int val){
	return lower_bound(b + 1,b + len + 1,val) - b;
}

struct ZXS{
	int cnt;
	vector sum,L,R,T;
	ZXS(int n):cnt(0),sum(n * 40),L(n * 40),R(n * 40),T(n + 5) {}
	
	int build(int l,int r){
		int rt = ++cnt;
		sum[rt] = 0;
		int mid = l + r >> 1;
		if(l > 1;
		if(l = r) return l;
		int x = sum[L[rt]] - sum[L[lt]];
		int mid = l + r >> 1;
		if(x >= k) return query(L[lt],L[rt],l,mid,k);
		else return query(R[lt],R[rt],mid + 1,r,k - x);
	}
};

int main(){
	int n = rd();
	int q = rd();
	for(int i = 1;i

[可持久化权值线段树] [模板] [数组版本]

标签：inline 持久化 max c++ str while for div 版本

原文地址：https://www.cnblogs.com/hznumqf/p/14489715.html

上一篇：03-Java异常面试题

下一篇：java 单例模式模式实现

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[可持久化权值线段树] [模板] [数组版本]
文章链接：http://soscw.com/index.php/essay/92725.html

亲，登录后才可以留言！

[可持久化权值线段树] [模板] [数组版本]

[可持久化权值线段树] [模板] [数组版本]

代码

评论

热门文章

推荐文章

最新文章

置顶文章