树链剖分

原理：将一棵树剖分成一条条的链，从而降低时间复杂度

首先会一个线段树，书完成剖分后，用来维护每一条的信息。

#include <bits/stdc++.h>
typedef int intt;
#define int long long
#define lc k << 1
#define rc k << 1 | 1
const int M = 2e6 + 10;
using namespace std;
int n,m,ans;
int a[M];
struct node{
	int l,r;
	int sum;
	int lazy;
}t[M << 2];
void Pushup(int k){
	t[k].sum = t[lc].sum + t[rc].sum;
}
void Pushdown(int k){
	if(t[k].lazy){
		t[lc].lazy += t[k].lazy;
		t[rc].lazy += t[k].lazy;
		t[lc].sum += (t[lc].r - t[lc].l + 1) * t[k].lazy;
		t[rc].sum += (t[rc].r - t[rc].l + 1) * t[k].lazy;
		t[k].lazy = 0;
	}
}
void Build(int k,int l,int r){
	t[k].l = l,t[k].r = r;
	if(l == r){
		t[k].sum = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	Build(lc,l,mid);
	Build(rc,mid + 1,r);
	Pushup(k);
}
void Modify(int k,int l,int r,int d){
	if(t[k].r < l || t[k].l > r) return;
	if(t[k].l >= l && t[k].r <= r){
		t[k].lazy += d;
		t[k].sum += (t[k].r - t[k].l + 1) * d;
		return ;
	}
	Pushdown(k);
	Modify(lc,l,r,d);
	Modify(rc,l,r,d);
	Pushup(k);
}
void Query(int k,int l,int r){
	if(t[k].r < l || t[k].l > r) return;
	if(t[k].l >= l && t[k].r <= r){
		ans += t[k].sum;
		return ;
	}
	Pushdown(k);
	Query(lc,l,r);
	Query(rc,l,r);
}
intt main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	Build(1,1,n);
	while(m--){
		int opt;
		cin >> opt;
		if(opt == 1){
			int x,y,k;
			cin >> x >> y >> k;
			Modify(1,x,y,k);
		}
		else {
			int x,y;
			cin >> x >> y;
			Query(1,x,y);
			cout << ans << "\n"; 
			ans = 0;
		}
	}
	return 0;
}