线段树模板

超高校级的毒瘤码风

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010; 
int n,m;
ll arr[N];
ll tree[N<<2]={0};//四倍于原数组 
ll lazy[N<<2];//lazy tag

/*懒标记下传函数*/
inline void func(ll node,ll l,ll r,ll k)
{
	lazy[node]=lazy[node]+k;
	tree[node]=tree[node]+k*(r-l+1);//区间统一改变，所以要加上区间总变化量，下同 
}
inline void push_down(int node,int l,int r)
{
	if(!lazy[node]) return ;
	ll mid=(l+r)>>1;
	int left_node=node<<1;
	int right_node=(node<<1)|1;
	if(lazy[node]==0) return ;
	func(left_node,l,mid,lazy[node]);
	func(right_node,mid+1,r,lazy[node]);
	lazy[node]=0;//tag推掉了，归零 
}

/*建树函数*/
void build_tree(int node/*节点编号*/,int start/*区间起点*/,int end/*区间终点*/) 
{
	lazy[node]=0;
	if(start==end)//递归出口：当区间无法继续细分 
	{
		tree[node]=arr[start];
		return ;
	}
	int mid=(start+end)>>1;
	int left_node=node<<1;
	int right_node=(node<<1)|1;
	build_tree(left_node,start,mid);
	build_tree(right_node,mid+1,end);
	
	tree[node]=tree[left_node]+tree[right_node];//维护线段树 
}

/*区间修改函数*/
void update_itv(int node,int start,int end,int l/*修改区间左端点*/,int r/*修改区间右端点*/,ll vol/*操作数(加上的数)*/)
{
	if(l<=start&&end<=r)
	{
//		cout<<start<<‘#‘<<end<<endl;
		tree[node]+=vol*(end-start+1);
		lazy[node]+=vol;//打懒标记 
		return ;
	}
	push_down(node,start,end);
	/*需要向下推 懒标记*/
	int mid=start+end>>1;
	int left_node=node*2;
	int right_node=(node*2)+1;
	if(l<=mid) update_itv(left_node,start,mid,l,r,vol);
	if(r>mid) update_itv(right_node,mid+1,end,l,r,vol);
	tree[node]=tree[left_node]+tree[right_node];//维护 
}

/*区间查询函数*/
ll query(int node,int start,int end,int l/*查询区间起点*/,int r/*查询区间终点*/)
{
	if(end<l||start>r) 
		return 0;//不在计算范围内
	if(l<=start&&end<=r)
		return tree[node];//当前区间被包含 
	int mid=start+end>>1;
	push_down(node,start,end);//推lazy 
	int left_node=node*2;
	int right_node=(node*2)|1;
	ll sum_left=query(left_node,start,mid,l,r);
	ll sum_right=query(right_node,mid+1,end,l,r);
	
	return sum_left+sum_right;//维护 
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&arr[i]);
	}
	build_tree(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int k,x,y,z;
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d%d%d",&x,&y,&z);
			if(x>y) swap(x,y);
			update_itv(1,1,n,x,y,z); 
//			cout<<
		}
		else 
		{
			scanf("%d%d",&x,&y);
			if(x>y) swap(x,y);
			printf("%lld\n",query(1,1,n,x,y));
		}
	}
}

线段树模板

原文：https://www.cnblogs.com/IzayoiMiku/p/13581611.html