基本线段树

admin

线段树是一种常用的数据结构，常常被用于统计区间和，最值等问题，它的基本思想是将区间(l,r)分成(l,m)和(m+1,r)两个基本等长区间，利用和，最大值等的特性（具有一定的传递性）进行统计，这样可以充分利用已经统计的有效信息，减少统计次数。比如整个区间是a1-a10有10个数，我们要多次查询(x,y)区间的数字和问题，我们先建立线段树，用结构体(l,r,s)表示区间(L R)之间的和为S，那么建立线段树如下：

admin

1. ///先决条件  位操作 树状数组（？）
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. const int mn=100;
   
5. 
   
6. int A[mn]; //原数组
   
7. int Sum[mn<<2];//Sum求和，开四倍空间
   
8. int Tag[mn<<2];//lazy标记
   
9. 
   
10. int n,k,x,y,z;
    
11. 
    
12. ///左儿子
    
13. int ls(int p){return (p<<1);}
    
14. ///右儿子
    
15. int rs(int p){return (p<<1|1);}
    
16. 
    
17. //PushUp函数更新节点信息，这里是求和
    
18. void PushUp(int p){        Sum[p]=Sum[ls(p)]+Sum[rs(p)];}
    
19. 
    
20. void f(int l,int r,int p,int k) ///lr区间的数加上k
    
21. {
    
22.         Tag[p]+=k;
    
23.         Sum[p]+=k*(r-l+1);
    
24. }
    
25. 
    
26. void PushDown(int l,int r,int p)
    
27. {
    
28.         int m=(l+r)>>1;
    
29.         f(l,m,ls(p),Tag[p]);
    
30.         f(m+1,r,rs(p),Tag[p]);
    
31.         Tag[p]=0;
    
32. }
    
33. 
    
34. void Update(int L,int R,int k,int l,int r,int p)
    
35. {
    
36.         if(L<=l && r<=R)
    
37.                 {
    
38.                         Sum[p]+=k*(r-l+1);
    
39.                         Tag[p]+=k;
    
40.                         return;
    
41.                 }
    
42.         PushDown(l,r,p);
    
43.         int m=(l+r)>>1;
    
44.         if(L<=m) Update(L,R,k,l,m,ls(p));
    
45.         if(R>m) Update(L,R,k,m+1,r,rs(p));
    
46. }
    
47. //Build函数建立线段树
    
48. void Build(int l,int r,int p)  //[l,r]表示当前节点区间，p表示当前节点的实际存储位置
    
49. {
    
50.         if(l==r)  //若到达叶节点
    
51.                 {
    
52.                         Sum[p]=A[l];//存储A数组的值
    
53.                         return;
    
54.                 }
    
55.         int m=(l+r)>>1;
    
56.         Build(l,m,ls(p));
    
57.         Build(m+1,r,rs(p));
    
58.         //更新信息
    
59.         PushUp(p);
    
60. }
    
61. 
    
62. int Query(int L,int R,int l,int r,int p)
    
63. ///[L,R]表示操作区间，[l,r]表示当前区间，p当前节点编号
    
64. {
    
65.         if(L<=l && r<=R)        return Sum[p];
    
66.         int m=(l+r)>>1;
    
67.         int ANS=0;
    
68.         if(L<=m) ANS+=Query(L,R,l,m,ls(p));
    
69.         if(R>m) ANS+=Query(L,R,m+1,r,rs(p));
    
70.         return ANS;
    
71. }
    
72. 
    
73. int  main()
    
74. {
    
75.         n=20;
    
76.         for (int i=1; i<=20; i++) A[i]=9+i;  ///假设20个数字是10-29
    
77.         Build(1,n,1);
    
78.         cin>>k; ///进行k次区间修改
    
79.         while (k--)
    
80.                 {
    
81.                         cin>>x>>y>>z; ///xy区间加上z
    
82.                         Update(x,y,z,1,n,1); ///
    
83.                         cout<<Query(x,y,1,n,1);///输出区间和
    
84.                 }
    
85.         return 0;
    
86. }

复制代码