线段树
欢迎在评论区留言和订阅专栏！
线段树是一个和树状数组差不多的数据结构，下面我就来讲一讲。
1.简介
线段树和树状数组都是在线算法(前面讲过)，与树状数组功能一样，是一种可以快速区间操作的算法。
线段树一共有4个步骤，分别是：建树、pushdown、指定点加值和查询，并且附有main函数。
2.代码
1.建树
int n,m,sum[100005],lazy[100005],a[100005];
//递归建树
void built(int node, int start, int end){
if (start == end) sum[node] = a[start];
else{
int mid = (start + end) / 2;
//二分
built(node*2+1, start, mid);
built(node*2+2, mid+1, end);
sum[node] = sum[node*2+1] + sum[node*2+2];
}
}
2.pushdown
void pushdown(int node, int start, int end){
if (lazy[node] != 0){
int mid = (start+end)/2;
sum[node*2+1] += lazy[node] * (mid-start+1);
sum[node*2+2] += lazynode] * (end-mid);
lazy[node*2+1] += lazy[node];
lazy[node*2+2] += lazy[node];
lazy[node] = 0;
}
}
3.指定点加值
void add(int node, i剩余60%内容，订阅专栏后可继续查看/也可单篇购买
c++算法大全 文章被收录于专栏
本专栏收集了c++大部分基础算法，附有简介和代码。
投递华为技术有限公司等公司10个岗位