博客

洛谷 P3372 【模板】线段树 1

/**
 *    author:  McFly
 *    created: 02.2022 
 *	  describ:  线段树				
**/
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll; //要开long long 

void tree_build( vector<ll>& v, vector<ll>& array, int left, int right, int pos ) 
/*
建树，单点插入 
left,right 是值在一维数组中下标的左右边界， index是值在数组中下标， pos是线段树某节点对应数组结构中位置下标 
*/
{ 
	if( left == right ) {
		v[pos] = array[left];
		return ;
	} 
	int mid = left + ( (right-left)>>1 ); //>>,<<是右结合的，一定记得套括号 
	tree_build( v,array,left,mid,pos<<1 ); //左右子树这样写，快捷又高档。 
	tree_build( v,array,mid+1,right,pos<<1|1 ); //方向别写反了 
	v[pos] = v[pos<<1] + v[pos<<1|1]; 
}

ll tree_search( vector<ll>& v, vector<ll>& lazy, int l, int r, 
				int aim_left, int aim_right, int pos ) 
/*
区间查询 
l,r是当前节点代表的左右边界， aim_left/right是目标区间， pos是线段树节点在v中的下标 
*/
{
	if( l == aim_left && r == aim_right ) {
		return v[pos];
	}
	int mid = (l+r)>>1; 
	if( lazy[pos] ) {
		lazy[pos<<1] += lazy[pos];
		lazy[pos<<1|1] += lazy[pos];
		v[pos<<1] += lazy[pos]*(mid-l+1);
		v[pos<<1|1] += lazy[pos]*(r-mid);
		lazy[pos] = 0;
	} 
	ll ret = 0;
	if( aim_left <= mid ) {
		ret += tree_search( v,lazy,l,mid,aim_left,min(mid,aim_right),pos*2 );
	}
	if( aim_right > mid ) {
		ret += tree_search( v,lazy,mid+1,r,max(aim_left,mid+1),aim_right,pos*2+1 );
	}
	//注意这里每次更新目标区间，一定要加min/max把区间写对了
	//或者前面特判改成(l<=aim_left&&r>=aim_right),同时下面递归时不改变目标区间 
	return ret;
}

ll tree_alert( vector<ll>& v, vector<ll>& lazy, int l, int r, 
				int aim_left, int aim_right, ll k, int pos )
/*
区间修改 
参数意义同search，事实上search就是alert的一部分 
*/
{
	/* 若当前节点区间与待求区间匹配，直接返回本节点值(k乘区间长度) */
	if( l == aim_left && r == aim_right ) {
		lazy[pos] += k;
		v[pos] += (r-l+1)*k;
		return v[pos];
	}
	int mid = l + (r-l)/2;
	/* lazy标记下传 */
	if( lazy[pos] ) {
		lazy[pos<<1] += lazy[pos];
		lazy[pos<<1|1] += lazy[pos];
		v[pos<<1] += lazy[pos]*(mid-l+1);
		v[pos<<1|1] += lazy[pos]*(r-mid);
		lazy[pos] = 0;
	}
	ll lc = v[pos<<1],rc = v[pos<<1|1];
	/* 处理子树 */ 
	if( aim_left <= mid ) {
		lc = tree_alert( v,lazy,l,mid,aim_left,min(mid,aim_right),k,pos<<1 );
	}
	if( aim_right > mid ) {
		rc = tree_alert( v,lazy,mid+1,r,max(aim_left,mid+1),aim_right,k,pos<<1|1 );
	}
	/* 子树处理完后更新节点 */
	v[pos] = lc+rc;
	return v[pos];
}

int main()
{
	ios_base::sync_with_stdio(false),cin.tie(0); //cin/cout一定要开这个 
	int n, m;
	cin >> n >> m;
	vector<ll> array(n+1);		//暂存数组  
	vector<ll> v(n*4); 		//线段树 
	vector<ll> lazy(n*4);   //lazy标记 , 注意下标都从1开始（便于左右子树下标的确定） 
 	/* 建树 */
	for ( int i = 0; i < n; i++ ) cin >> array[i+1];
	tree_build( v, array, 1, n, 1 ); 
	int option,x,y,k;
	while( m-- ) {
		cin >> option;
		/* 1为更新区间值，2为输出区间和 */
		if( option == 1 ) {
			cin >> x >> y >> k;
			tree_alert( v,lazy,1,n,x,y,k,1);
		}
		else {
			cin >> x >> y;
			cout << tree_search( v,lazy,1,n,x,y,1 ) << endl;
		}
	}
 }