线段树Segment Tree
迷茫
线段树学习
问题导入
给定一个长度为n的数组，有m次操作，每次操作可能如下：
1，修改 a[i] 的值
2，求连续一段区间的和
3， 求连续一段区间的最大值/最小值
4，给区间的每个数加上k
5，查询a[i] 的值。
如果对这个数据进行模拟操作，最差时间复杂度可能为O(mn) , 如果数据量非常大，处理起来非常容易超时。所以采用一种数据结构来优化。所以线段树就诞生了。
线段树
线段树类似下图树状结构，用蒟蒻语说，就是“树状区间和”，即将一个二分过程表现出来。通过改变大区间的值，来实现短时区间计算。时间复杂度可以优化到O(logn)
3XhpeU.png
线段树操作
1.建树
建树采用二分的方法
void build(int l,int r,int node)
{
if(l==r)
{
scanf("%d",&tree[node]);
maxn[node] = tree[node];
return;
}
int mid = (l+r)>>1;
build(l,mid,node*2);
build(mid+1,r,node*2+1);
tree[node] = tree[node<<1] + tree[node<<1 | 1];
maxn[node] =max( maxn[node<<1] , maxn[node<<1|1] );
}2.单点修改
//单点修改
void change(int index,int key,int l,int r,int node)
{
if(l==r)
{
tree[node] = key;
maxn[node] = key;
return ;
}
// push_down(node,mid-l+1,r-mid); 若既有点更新又有区间更新，需要这句话
int mid = (l+r)>>1;
if(index<=mid)
change(index,key,l,mid,node<<1);
else
{
change(index,key,mid+1,r,node<<1|1);
}
tree[node] = tree[node<<1] +tree[node<<1|1];
maxn[node] = max(maxn[node<<1] ,maxn[node<<1|1]);
}3.区间和
//区间和
int query_sum(int L,int R,int l,int r,int node)
{
if(L<=l&&r<=R)
{
return tree[node];
}
int mid = (l+r)>>1;
int sum = 0;
if(L<=mid)
{
sum+=query_sum(L,R,l,mid,node*2);
}
if(mid+1<=R)
{
sum+=query_sum(L,R,mid+1,r,node*2+1);
}
return sum;
}4.区间更新
void change_range(int node,int l,int r,int L,int R,int key)
{
if(L<=l&&r<=R)
{
lazy[node] +=1LL*key;
tree[node]+=1LL*(r-l+1)*key;
return ;
}
//push_down(node,l,r);
int mid = (l+r)>>1;
if(l<=mid)
change_range(node<<1,l,mid,L,R,key);
if(mid<r)
change_range(node<<1|1,mid+1,r,L,R,key);
tree[node] = tree[node<<1] +tree[node<<1|1];
}未完待续。。。。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-03-07|，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
