线段树

欢迎在评论区留言和订阅专栏！

线段树是一个和树状数组差不多的数据结构，下面我就来讲一讲。

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