线段树_单点询问、修改_入门
detect
2018-07-21 17:03:28
资料感谢：https://pks-loving.blog.luogu.org/senior-data-structure-qian-tan-xian-duan-shu-segment-tree
****一、简介线段树****
psps : _此处以询问区间和为例。实际上线段树可以处理很多符合结合律的操作。（比如说加法，a[1]+a[2]+a[3]+a[4]=(a[1]+a[2])+(a[3]+a[4])）
线段树之所以称为“树”，是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的（包括 RMQRMQ 、 RSQRSQ 问题等。
对于每一个子节点而言，都表示整个序列中的一段子区间；对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。
有没有觉得很熟悉？
对，线段树就是分块思想的树化，或者说是对于信息处理的二进制化——用于达到 O(logn)O(logn) 级别的处理速度， loglog 以 22 为底。（其实以几为底都只不过是个常数，可忽略)。而分块的思想，则是可以用一句话总结为：通过将整个序列分为有穷个小块，对于要查询的一段区间，总是可以整合成 kk 个所分块与 mm 个单个元素的信息的并 (0<=k,m<=\sqrt{n})(0<=k,m<=
n
) 。
但普通的分块不能高效率地解决很多问题，所以作为 loglog 级别的数据结构，线段树应运而生。
其实，虽然线段树的时间效率要高于分块但是实际上分块的总合并次数不会超过 \sqrt{n}
n
但是线段树在最坏情况下的合并次数显然是要大于这个时间效率的。
但是毕竟也只是一个很大的常数而已
HoweverHowever ,虽说如此，分块的应用范围还是要广于线段树的，因为虽然线段树好像很快，但是它只能维护带有结合律的信息，比如区间 max/minmax/min 、 sumsum 、 xorxor 之类的，但是不带有结合律的信息就不能维护（且看下文分解）；而分块则灵活得多，可以维护很多别的东西,因为实际上分块的本质就是优雅的暴力qwq。
其实越暴力的算法可以支持的操作就越多、功能性就越强呐！你看 n^2n
2
的暴力几乎什么都可以维护。
------------
好了，那吗作为入门（~~其实是懒标记太难~~），今天在这里就只讲讲：
****1:区间修改_单点求和_延迟标记****
****2:单点修改_区间求和****
直接上代码了，毕竟思路都在代码里。
No.1 单点修改_区间求和
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[400005],s[400005],e,bi;//s数组作为区间和
int getint()//读入优化
{
int summ=0,f=1;
char ch;
for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
if(ch=='-')
{
f=-1;
ch=getchar();
}
for(;isdigit(ch);ch=getchar())
summ=(summ<<3)+(summ<<1)+ch-48;
return summ*f;
}
void build(int k,int l,int r)//构建线段树
{
if(l==r)//如果是叶节点
{
s[k]=a[l];//那么区间和就是它自己
return;
}
int mid=(l+r)>>1;
build(k*2,l,mid);//往左递归
build(k*2+1,mid+1,r);//往右递归
s[k]=s[2*k]+s[2*k+1];//在左右递归完成后更新它们的祖先
}
void onechange(int k,int l,int r,int p,int v)//单点修改
{
if(l>p||r<p)///特判
return;
if(l==p&&l==r)//如果找到了那个点
{
s[k]+=v;//更新
return;
}
int mid=(r+l)/2;
onechange(k*2,l,mid,p,v);
onechange(k*2+1,mid+1,r,p,v);
s[k]=s[2*k]+s[2*k+1];//重新跟新
}
int question(int k,int l,int r,int x,int y)//区间查询
{
if(x>r||y<l) return 0;
if(l>=x&&r<=y)
{
return s[k];//完全包括直接返回区间和
}
int mid=(l+r)>>1;
int sum=0;
sum+=question(k*2,l,mid,x,y);
sum+=question(k*2+1,mid+1,r,x,y);//递归求所有区间和
return sum;
}
int main()//main里面就是模拟了，没什么好讲
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a[i]=getint();
}
build(1,1,n);
int v;
for(int i=1;i<=m;i++)
{
int x,y;
bi=getint();
if(bi==1)
{
x=getint();
y=getint();
v=getint();
for(int j=x;j<=y;j++)
onechange(1,1,n,j,v);
}
else{
x=getint();
y=getint();
cout<<question(1,1,n,x,y)<<endl;
}
}
return 0;
}
```
------------
No.2 区间修改_单点求和_延迟标记
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[400005],s[400005],add[400007],e,bi;
int getint()
{
int summ=0,f=1;
char ch;
for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
if(ch=='-')
{
f=-1;
ch=getchar();
}
for(;isdigit(ch);ch=getchar())
summ=(summ<<3)+(summ<<1)+ch-48;
return summ*f;
}
void build(int k,int l,int r)
{
if(l==r)
{
add[k]=a[l];//初始建树时，该标记赋初值。（其实一个for循环也可以？
return;
}
int mid=(l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
//add[k]=add[2*k]+add[2*k+1];
}
void exchange(int k,int l,int r,int x,int y,int v)
{
if(l>y||r<x)
return;
if(l>=x&&r<=y)//完全包括
{
add[k]+=v;//整体+v
return;
}
int mid=(r+l)/2;
exchange(k*2,l,mid,x,y,v);
exchange(k*2+1,mid+1,r,x,y,v);//一直递归往下找，也不用更新别的了。
}
int question(int k,int l,int r,int x)//求单点，就是求根节点到所求点标记总和。
{
if(r==l) return add[k];
int mid=(l+r)/2;
if(x<=mid) return question(k*2,l,mid,x)+add[k];
else return question(k*2+1,mid+1,r,x)+add[k];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a[i]=getint();
}
build(1,1,n);
int v;
for(int i=1;i<=m;i++)
{
int x,y;
bi=getint();
if(bi==1)
{
x=getint();
y=getint();
v=getint();
exchange(1,1,n,x,y,v);
}
else{
x=getint();
cout<<question(1,1,n,x)<<endl;
}
}
return 0;
}
```
今天就讲那么多了，很快就会跟新懒标记了。。。
****敬请期待......****