关于线段树基础 - 你的小垃圾
source link: https://www.cnblogs.com/zch061023/p/16305768.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
关于线段树基础
首先明白什么是线段树：
线段树是一棵二叉树，每个节点表示序列上的一段区间，其中根节点表示区间[1,n]
从根节点开始，只要区间长度不为1，就将区间划分为两半，并分给两个子结点
如下图，就是n=8的线段树：
当节点表示区间[l,r]，当l≠r时，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]
当l=r时，该节点为叶子节点
线段树的基本性质：
性质1.总节点数为2n-1
性质2.线段树并不一定是一棵完全二叉树，最后一层可能为空，且空结点的个数可能能达到2n个，因此最好开一棵4n的数组来避免LE
性质3.层数约为
，即每个叶节点到根节点的距离约为
个节点组合而成性质
性质4.任何区间都可以用不超过2
个结点组成
线段树工作原理：
我们先在线段树的每个节点都储存该区间的总和。假设起始都为0
对于操作1，令A[x]加上y，我们先从根节点出发，找到[x,x]，比如x=3
此时，路径上每个区间都包含x
接下来，将这些区间储存的总和都加上y，比如y=4
这就是单点修改的工作原理，跟树状数组有些相似之处，即修改一个点会对其祖先有同样效果的影响，即要将其所有的祖先结点都通过修改的方式加上同样的效果来保证影响的后效性。
问题2：询问区间[x,y]的总和
就是寻找这个区间包含的最长且完整的、没有交集的若干区间。
下面是线段树的模板：
代码如下：
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4
5 #define ll long long
6
7 inline int get()//快读
8 {
9 char c;
10 int sign=1;
11 while((c=getchar())<'0'||c>'9')
12 {
13 if(c=='-')
14 {
15 sign=-1;
16 }
17 }
18 int res=c-'0';
19 while((c=getchar())>='0'&&c<='9')
20 {
21 res=res*10+c-'0';
22 }
23 return res*sign;
24 }
25
26 const int N=1e5+5;
27 int n,m,a[N];
28 int add[N*4];
29 ll sum[N*4];
30
31 void build(int k,int l,int r)//建树
32 {
33 if(l==r)//区间长度为1，是叶节点，给它赋值
34 {
35 sum[k]=a[l];
36 return;
37 }
38 int mid=l+r>>1;
39 build(k<<1,l,mid);//建他的左儿子
40 build(k<<1|1,mid+1,r);//建他的右儿子
41 sum[k]=sum[k<<1]+sum[k<<1|1];//他的区间和等于他两个儿子的和
42 }
43
44 int Add(int k,int l,int r,int v)//区间加并更新值
45 {
46 add[k]+=v;//给懒标记更新值
47 sum[k]+=(ll)v*(r-l+1);//给区间和更新值
48 }
49
50 void pushdown(int k,int l,int r,int mid)//进行懒标记的下放
51 {
52 if(add[k]==0)
53 {
54 return ;//如果懒标记是0就直接跳过，不用在乎他
55 }
56 Add(k<<1,l,mid,add[k]);//懒标记让他的两个儿子更新值
57 Add(k<<1|1,mid+1,r,add[k]);
58 add[k]=0;//最后要将懒标记赋值0，以便下次懒标记更新值时不会受到上一次标记的影响
59 }
60
61 ll query(int k,int l,int r,int x,int y)//询问区间和，其中l和r代表的是当前访问的区间端点，x和y代表的是想要求和的区间端点
62 {
63 if(l>=x&&r<=y) return sum[k];//如果当前访问的区间在求和区间以内，就将它的值返回给res
64 int mid=l+r>>1;
65 ll res=0;
66 pushdown(k,l,r,mid);//先进行标记下放，确保当前访问的区间是最新的
67 if(x<=mid) res+=query(k<<1,l,mid,x,y);
68 if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
69 return res;
70 }
71
72 int modify(int k,int l,int r,int x,int y,int v)//给区间的每个元素加值得操作
73 {
74 if(l>=x&&r<=y) return Add(k,l,r,v);//就是给它这个区间做标记
75 int mid=l+r>>1;
76 pushdown(k,l,r,mid);
77 if(x<=mid) modify(k<<1,l,mid,x,y,v);
78 if(y>mid) modify(k<<1|1,mid+1,r,x,y,v);
79 sum[k]=sum[k<<1]+sum[k<<1|1];
80 }
81
82 int main()
83 {
84 n=get(),m=get();
85 for(int i=1;i<=n;++i)
86 {
87 a[i]=get();
88 }
89 build(1,1,n);
90 ll a1,b,c,d,e,f;
91 while(m--)
92 {
93 scanf("%lld",&a1);
94 switch(a1)
95 {
96 case 1:{
97 scanf("%lld%lld%lld",&b,&c,&d);
98 modify(1,1,n,b,c,d);
99 break;
100 }
101 case 2:{
102 scanf("%lld%lld",&e,&f);
103 printf("%lld\n",query(1,1,n,e,f));
104 break;
105 }
106 }
107 }
108 return 0;
109 }
以上就是线段树的基本操作了，上面代码会存疑的地方大多都有注释，最后只解释有关懒标记的操作：
在没有懒标记的时候，之前修改的位置都要立即更新，所以无形之中复杂度就高了很多，刺死就突出了懒标记的作用：
懒标记，顾名思义就是很懒的标记，每当我进行区间加的操作时，它起到了一个给目标区间记录的作用，即区间不会立即修改，而是将每次的操作记录并累计下来，只有当访问的元素包括此元素的时候才会将此元素依照对应的懒标记进行单点修改，也就从原来的
直接降成
，复杂度降了很多诶！
那好吧，由于本人能力有限，目前还无法解决关于区间乘除的问题，敬请期待！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK