一个算法要有模版题
先来说一下线段树，大概是个什么东西。
它每个节点存的都是一个区间。
假设当前节点编号是 now ，存的区间是 l ~ r 。
他的左儿子编号是 now\times2 ，右儿子编号是 now\times2+1 。
然后我们令 mid=(l+r)/2 。
那么左儿子存的区间是 l ~ mid ，那么右儿子存的区间是 mid+1 ~ r 。
初始化
他会给你一个序列，我们先要吧序列存入线段树。
然后如何递归建树呢。
这个比较简单，直接带到代码里讲。
其中 l,r 是区间， now 是当前节点编号。
tree 数组存的是当前节点的区间和。
void build(int l,int r,int now)
{
if(l==r)//区间只有一个点
{
tree[now]=a[l];//赋值
return;
}
int mid=(l+r)/2;
build(l,mid,now*2);//建左儿子
build(mid+1,r,now*2+1);//建右儿子
push_up(now);//更新祖先
}
我们发现有个 push_up 函数。
这是用来更新祖先的。
在更新祖先之前我们求出了它的两个儿子的区间和。
所以把他们相加就是祖先的区间和。
因为它的区间就拆成了两个儿子的两个区间。
那 push_up 函数就好写了。
void push_up(int now)
{
tree[now]=tree[now*2]+tree[now*2+1];//上面说个now*2和now*2+1是它的两个儿子
}
区间加
我们先考虑单点加。
就是不断二分得到存那个位置的节点，不难发现这个节点是叶子节点，所以直接加。
复杂度是 O(logn) 。
那如果是区间加呢？
那复杂度不成了 O(nlogn) 那不是比暴力还差了。
这里我们就要引入一个新的概念，懒标记。
记 tag_{now} 表示 now 这个节点被修改加了多少，但是还没有下传的。
然后要用到的时候下传，下传是 O(1) 的，我们可以到时候看代码。
直接放下传代码。
push_down 就是用来懒标记下传的，我们后面会讲。
void update(int l,int r,int nl,int nr,int now,int k)
{
if(nl<=l&&r<=nr)//如果这个点的区间，被要找的区间包含了
{
tree[now]+=(r-l+1)*k;//区间内有r-l+1个数，每个数+k，所以就是+(r-l+1)*k
tag[now]+=k;//懒标记，表示多了+k要下传
return;
}
push_down(l,r,now);//懒标记下传
int mid=(l+r)/2;
if(mid>=nl) update(l,mid,nl,nr,now*2,k);//如果左半边有答案需要的数
if(mid<nr) update(mid+1,r,nl,nr,now*2+1,k);//如果又半边有答案需要的数
push_up(now);//更新祖先
}
下面看 push_down。
void push_down(int l,int r,int now)
{
int mid=(l+r)/2;
lazy(l,mid,now*2,tag[now]);//更新它的左儿子
lazy(mid+1,r,now*2+1,tag[now]);//更新它的右儿子
tag[now]=0;//懒标记清空
}
lazy函数是更新儿子的。
void lazy(int l,int r,int now,int k)//k是传过来的没有下传的tag
{
tree[now]+=k*(r-l+1);//区间内有r-l+1个数，每个数+k，所以就是+(r-l+1)*k
tag[now]+=k;//懒标记还是要下传
}
这里有人就会问了，两个 if 有可能都会进去，那复杂度不是 O(n) 的吗？
可以发现，如果进去了第一个 if 那么下一次，如果进去第二个或不进去，肯定是被覆盖的可以直接 return。
进去第二个 if 也是类似的。
区间求和
和区间加类似，直接看代码吧。
int query(int l,int r,int nl,int nr,int now)
{
int ans=0;
if(nl<=l&&r<=nr) return tree[now];//包含直接return
push_down(l,r,now);//下传懒标记
int mid=(l+r)/2;
if(mid>=nl) ans+=query(l,mid,nl,nr,now*2);
if(mid<nr) ans+=query(mid+1,r,nl,nr,now*2+1);
//这里和上面一样
return ans;
}
怎么样你听懂了吗。
求赞