线段中的动态问题知识点（【线段树】动态开点）

使用场景

维护的区间太大以至于 \(4N\) 存不下 
    
    
  ，通常是权值线段树； 维护的区间下标存在负数；

时间复杂度

全部开点
     


     


     
，则 \(O(2N - 1)\) 每递归一次 




 




 




，最多开点 \(O(\log_N)\)  

   

   

 ，若调用 \(M\) 次
     

     

     ， \(O(M\log_N)\)

原理

若一段子区间 [L,R] 对应的线段树节点为 cur   




  




  




，当不需要递归时 


  


  


，就不建点；

当调用 addtag() 时
     
     
     ，新建节点    
    
    
。

注意事项

没有 build 函数； addtag 的节点 cur 要取址； 有负数区间时   




   




   



， mid = (lt + rt - 1) / 2； 根节点 root 为 \(1\)

代码

#include<bits/stdc++.h> using namespace std; #define lc(x) tree[x].lc #define rc(x) tree[x].rc #define sum(x) tree[x].val #define tag(x) tree[x].tag const int N = 1e5 + 5; int n, m, tot; long long a[N] struct node { long long tag, val; int lc, rc; }tree[N*2]; void addtag(int &cur, int lt, int rt, long long val) //注意取值符 { if(cur == 0) //结点不存在就新建立 cur = ++tot; sum(cur) += (rt - lt + 1) * val; tag(cur) += val; return ; } void pushup(int cur) { sum(cur) = sum(lc(cur)) + sum(rc(cur)); return ; } void pushdown(int cur, int lt, int rt) { if(lt >= rt) return ; int mid = (lt + rt - 1) / 2; addtag(lc(cur), lt, mid, tag(cur)); addtag(rc(cur), mid+1, rt, tag(cur)); tag(cur) = 0; return ; } void update(int cur, int lt, int rt, int qx, int qy, long long val) { if(qy < lt || qx > rt) //不归cur管 return ; if(qx <= lt && rt <= qy) //cur管辖的区间要全部修改 



 



 



，直接打懒标记 { addtag(cur, lt, rt, val); return ; } pushdown(cur, lt, rt); int mid = (lt + rt - 1) / 2; update(lc(cur), lt, mid, qx, qy, val); update(rc(cur), mid+1, rt, qx, qy, val); pushup(cur); return ; } long long query(int cur, int lt, int rt, int qx, int qy) //结点    
    
    
、管辖的区间范围  


     


     


  、询问的区间范围 { if(qy < lt || qx > rt) return 0; if(qx <= lt && rt <= qy) return sum(cur); pushdown(cur, lt, rt); int mid = (lt + rt - 1) / 2; return query(lc(cur), lt, mid, qx, qy) + query(rc(cur), mid+1, rt, qx, qy); } int main() { cin >> n >> m; int root = 1; //根结点编号 tot = 1; //总结点数量 for(int i = 1; i <= n; i++) { int x; cin >> x; update(root, 1, n, i, i, x); } for(int i = 1; i <= m; i++) { int opt, x, y, val; cin >> opt >> x >> y; if(opt == 1) { cin >> val; update(root, 1, n, x, y, val); //结点编号


 




 




 
、管辖的左右边界   

   

   

、修改的左右边界   

     

     

 、修改的值 } else cout << query(root, 1, n, x, y) << "\n"; //结点编号



  




  




  、管辖的左右边界  


  


  


、询问的左右边界 } return 0; }

例题

Luogu P3372

Luogu P2781

Luogu P5459

P5459题解

简要题意

\(n\) 个数              ，求有多少个区间的和在 \(L\) 和 \(R\) 之间  


     


     


  。

思路

本题是求方案树
    




    




    


，由题面有关数的和可以得知我们需要一种值域线段树














，

注意到 \(L\) 与 \(R\) 的范围较大              ，所以需要用动态开点解决此类问题
     



     



     

，

我们可以先建一个前缀和














，自然前缀和 res[] 需要满足 L <= res[j] - res[i] <= R  
    
    
  ，可转化为 res[j] - R <= res[i] <= res[j] - L 
     


     


     
，

于是 




 




 




，可以以每个前缀为节点 

   

   

 ，用线段树维护在一个区间中的方案数
     

     

     ，

这道题便做完了


 




 




 
。

AC 代码 #include<bits/stdc++.h> using namespace std; #define lc(x) tree[x].lc #define rc(x) tree[x].rc #define sum(x) tree[x].val #define tag(x) tree[x].tag const int N = 5e6 + 5; const long long M = 1e10 + 5; int n, m, tot; long long a[N], res[N]; struct node { long long tag, val; int lc, rc; }tree[N*2]; void addtag(int &cur, int lt, int rt, long long val) //注意取值符 { if(cur == 0) //结点不存在就新建立 cur = ++tot; sum(cur) += (rt - lt + 1) * val; tag(cur) += val; return ; } void pushup(int cur) { sum(cur) = sum(lc(cur)) + sum(rc(cur)); return ; } void pushdown(int cur, long long lt, long long rt) { if(lt >= rt) return ; long long mid = (lt + rt - 1) / 2; addtag(lc(cur), lt, mid, tag(cur)); addtag(rc(cur), mid+1, rt, tag(cur)); tag(cur) = 0; return ; } void update(int cur, long long val, int add, long long L = -M, long long R = M) { if(val < L || val > R) return ; if(L == R) { addtag(cur, L, R, add); return ; } pushdown(cur, L, R); long long mid = (L + R) >> 1; update(lc(cur), val, add, L, mid); update(rc(cur), val, add, mid+1, R); pushup(cur); return ; } long long query(int cur, long long ql, long long qr, long long L = -M, long long R = M) { if(qr < L || ql > R) return 0; if(ql <= L && qr >= R) return sum(cur); pushdown(cur, L, R); long long mid = (L + R) >> 1; return query(lc(cur), ql, qr, L, mid) + query(rc(cur), ql, qr, mid + 1, R); } signed main() { int ri, le; cin >> n >> le >> ri; int root = 1; tot = 1; for(int i = 1; i <= n; i++) { int x; cin >> x; res[i] = res[i - 1] + x; } long long ans = 0; update(root, res[0], 1); for (int i = 1; i <= n; ++i) { ans += query(root, res[i] - ri, res[i] - le); update(root, res[i], 1); } cout << ans; return 0; }