主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
数据结构——动态开点线段树
最后更新于 2025-07-31 07:25:39
作者
ICE__LX
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
- 本文章历史些许久远， KaTeX 的错误不可避免。 ### 首先，线段树是什么？ 这！~~就是线段树~~！  ### 这是正文 咳咳……线段树 是一种将 区间查询、区间修改、单点修改 的时间复杂度优化到 **log 级别**的 数据结构。 …… 别看我把它说得这么 6，事实上在考场上完全记不起来（个人因素），论记忆性和通用性，~~还得是分块~~。 理论上的东西我懒得讲了，与其看文字，相信大家更想直接watching，所以这个up的视频自己康一下，方便后续的教学（就不用康她代码实现了，她用的是Pascal）。  可以从她的教学中理解线段树的，继续往下学，这里讲 c++ 代码实现。 这个视频里的线段树是按堆式建树的，堆式建树呢有个优点，就是前期好学，但到后期用起来反倒有些麻烦，为什么呢，因为它需要开4n的空间，这是堆式建树最大的缺点。 当然，对于初学者，堆式建树确实好理解，可以看看[这篇文章](https://shimo.im/docs/loqeWWXX5mcdeAnz/read)，再理一理线段树的理论知识，补一补前置知识：离散数学，顺便理解一下，为什么堆式建树需要 4n 的空间。 那么，接下来要讲的，就是 ### 链式建树 链式建树具体是怎么实现的呢，它比堆式建树强在哪里呢？ 首先，链式建树是用 vecor 实现的，虽然 push_back 的常数指数阶增长确实鸡肋，但依旧比4n强！它能保证动态分配空间，合理分配内存。如果你嫌弃vector，自主开 2n 的空间，手写一个 push_back 也不是不行。 而且，堆式建树对孩子的访问是通过乘2，乘2加1实现的，而链式建树对孩子的访问是直接的，方便快捷。 最后提一下，**堆式建树与链式建树只是建树和访问孩子的方式不同，在区间查询、区间修改等方面完全一致，对于其算法，仅需更改其访问孩子的方式即可。** ### 下面是代码实现 变量名与堆式建树文章不同，还请谅解。 首先，为了维护每一个结点的信息，定义一个Segment_Tree类： ```cpp struct Segment_Tree{ int l,r;//区间的范围 l~r int child_l,child_r;//左右孩子的下标 int ans;//区间和 int lazy_add=0,lazy_mul=1;//加法运算与乘法运算的lazy标记 void merge(int idx);//维护区间值的成员函数 Segment_Tree() { } Segment_Tree(int value, int idx) {//用于建树的构造函数（用于叶子结点） ans = value; l = r = idx; child_l=child_r=-1; } }; vector<Segment_Tree>tree; ``` 由于建树无需维护太多信息，为了提高建树效率，单独定义一个维护函数用于建树（合并孩子结点）。 ```cpp Segment_Tree merge(int l,int r){//合并左右孩子的信息构建父结点 Segment_Tree tmp; tmp.child_l=l,tmp.child_r=r;//记录左右孩子的下标 tmp.l=tree[l].l,tmp.r=tree[r].r;//区间范围：左孩子的边界l~右孩子的边界r tmp.ans=tree[l].ans+tree[r].ans;//合并孩子结点的区间和 return tmp; } ``` 链式建树，用一个变量root记录根节点的下标（其实就是数组最后一个元素） ```cpp int build_tree(int l,int r,int *a){//链式建树 if(l==r){//若达到叶子结点 tree.push_back(Segment_Tree(a[l],l));//加入数组 return tree.size()-1;//返回其下标 } int mid=(l+r)/2; //通过孩子结点的信息合并出父结点的信息 tree.push_back(merge(build_tree(l,mid,a),build_tree(mid+1,r,a))); return tree.size()-1;//返回其下标 } void build(int l,int r,int *a){//调用链式建树，记录根结点下标 root=build_tree(l,r,a);//其实返回的就是tree.size()-1 } ``` 维护区间值的成员函数（与堆式建树文章不符，看各位是否需要了） ```cpp void Segment_Tree::merge(int idx){ int mid=(l+r)/2; tree[child_l].ans=(tree[child_l].ans*lazy_mul+lazy_add*(mid-l+1))%mod; tree[child_r].ans=(tree[child_r].ans*lazy_mul+lazy_add*(r-mid))%mod; tree[child_l].lazy_mul=(tree[child_l].lazy_mul*lazy_mul)%mod; tree[child_r].lazy_mul=(tree[child_r].lazy_mul*lazy_mul)%mod; tree[child_l].lazy_add=(tree[child_l].lazy_add*lazy_mul+lazy_add)%mod; tree[child_r].lazy_add=(tree[child_r].lazy_add*lazy_mul+lazy_add)%mod; lazy_mul=1; lazy_add=0; } ``` ### 最后，献上[P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)的题解，便于大家参考与理解 不想敲区间加，区间乘、区间查询的注解了，所以干脆全删了。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,a,b) for(int i=a;i<=b;i++) const int maxn=INT_MAX; const double INF=DBL_MAX; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=x*10+ch-48; ch=getchar(); } return x*f; } struct Segment_Tree{ int l,r; int child_l,child_r; int ans; int lazy_add=0,lazy_mul=1; void merge(int idx); Segment_Tree() { } Segment_Tree(int value, int idx) { ans = value; l = r = idx; child_l=child_r=-1; } }; int mod,root; vector<Segment_Tree>tree; void Segment_Tree::merge(int idx){ int mid=(l+r)/2; tree[child_l].ans=(tree[child_l].ans*lazy_mul+lazy_add*(mid-l+1))%mod; tree[child_r].ans=(tree[child_r].ans*lazy_mul+lazy_add*(r-mid))%mod; tree[child_l].lazy_mul=(tree[child_l].lazy_mul*lazy_mul)%mod; tree[child_r].lazy_mul=(tree[child_r].lazy_mul*lazy_mul)%mod; tree[child_l].lazy_add=(tree[child_l].lazy_add*lazy_mul+lazy_add)%mod; tree[child_r].lazy_add=(tree[child_r].lazy_add*lazy_mul+lazy_add)%mod; lazy_mul=1; lazy_add=0; } Segment_Tree merge(int l,int r){ Segment_Tree tmp; tmp.child_l=l,tmp.child_r=r; tmp.l=tree[l].l,tmp.r=tree[r].r; tmp.ans=(tree[l].ans+tree[r].ans)%mod; return tmp; } int build_tree(int l,int r,int *a){ if(l==r){ tree.push_back(Segment_Tree(a[l],l)); return tree.size()-1; } int mid=(l+r)/2; tree.push_back(merge(build_tree(l,mid,a),build_tree(mid+1,r,a))); return tree.size()-1; } void build(int l,int r,int *a){ root=build_tree(l,r,a); } int subtree_query(int l, int r, int idx) { Segment_Tree& x = tree[idx]; if (x.r < l || x.l> r) { return 0; } if (x.l>= l && x.r<= r) { return x.ans; } x.merge(idx); return (subtree_query(l, r, x.child_l)+subtree_query(l, r, x.child_r))%mod ; } int query(int l, int r) { return subtree_query(l-1, r-1, root); } void subtree_add(int l, int r,int idx, int val){ Segment_Tree& x = tree[idx]; if (x.r < l || x.l> r) { return; } if (x.l>= l && x.r<= r) { x.lazy_add=(x.lazy_add+val)%mod; x.ans=(x.ans+val*(x.r-x.l+1))%mod; return ; } x.merge(idx); subtree_add( l, r,x.child_l, val); subtree_add( l, r,x.child_r, val); x.ans=(tree[x.child_l].ans+tree[x.child_r].ans)%mod; return ; } void add(int l, int r,int val) { subtree_add(l-1, r-1, root, val); } void subtree_mul(int l, int r,int idx, int val){ Segment_Tree& x = tree[idx]; if (x.r < l || x.l> r) { return; } if (x.l>= l && x.r<= r) { x.ans=(x.ans*val)%mod; x.lazy_mul=(x.lazy_mul*val)%mod; x.lazy_add=(x.lazy_add*val)%mod; return ; } x.merge(idx); subtree_mul( l, r,x.child_l, val); subtree_mul( l, r,x.child_r, val); tree[idx].ans=(tree[x.child_l].ans+tree[x.child_r].ans)%mod; return ; } void mul(int l, int r,int val) { subtree_mul(l-1,r-1,root,val); } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n,m; cin>>n>>m>>mod; int *a=new int[n+1]; for(int i=0;i<n;i++)cin>>a[i]; build(0,n-1,a); for(int i=0;i<m;i++){ int t; cin>>t; if(t==2){ int x,y,k; cin>>x>>y>>k; add(x,y,k); }else if(t==3){ int x,y; cin>>x>>y; cout<<query(x,y)<<'\n'; }else{ int x,y,k; cin>>x>>y>>k; mul(x,y,k); } } return 0; } ```
正在渲染内容...
点赞
0
收藏
0
