线段树

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

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, int start, int end, int l, int r, int v){
	if (l > end || r < start) return;
    
    if ((l <= start) && (r >= end))
    {
    	sum[node] += v*(end - start+1);
        lazy[node] += v;
        return;
    }
    
    pushdown(node, start, end);
    //二分
    int mid = (start+end)/2;
    add(node*2+1, start, mid, l, r, v);
    add(node*2+2, mid+1, end, l, r, v);
    sum[node] = sum[node*2+1]+sum[node*2+2];
}

4.查询

int checksum(int node, int start, int end, int l, int r){
	if (l > end || r < start) return 0;
    
    if ((l <= start) && (r >= end)) return sum[node];
    
    pushdown(node, start, end);
    //二分
    int mid = (start+end)/2;
    int left = checksum(node*2+1, start, mid, l, r);
    int right = checksum(node*2+2, mid+1, end, l, r);
    return left+right;
}

*附main

cin >> n >> m;

for (int i = 1; i <= n; i++){
	cin >> a[i];
}

Built(1, 1, n);//建树

for (int i = 1; i <= m; i++){
	int k = 0;
    
    cin >> k;
    
    if (1 == k){
    	int x, y, z;
        
        cin >> x >> y >> z;
        
        add(1, 1, n, x, y, z);
    }
    else{
    	int x, y;
        
        cin >> x >> y;
        
        cout << checksum(1, 1, n, x, y) << endl;
    }
}

return 0;

这就是线段树的全部了，点个赞呗。欢迎在评论区留言！