看错题-线段树

题目描述

给定一颗线段树，每次区间加一个x，如果每次在线段树区间加操作做完后，依次选一个叶子节点进入，然后一直走到根节点，问最后得到的期望值是多少。

小Y同学为了让题目更简单，对于n个整数，n是一个2^x2x的整数，来保证这个线段树是一棵满二叉树。

他现在想问你，每次给一段区间加上一个整数（每次操作对后续有影响），然后依次在线段树中选一个叶子节点，一直走到根节点，将一路经过的节点权值累加，问把每一个叶子节点选择一遍后的全部的总和是多少。

Input

第一行整数 n,m, 表示线段树维护的原序列的长度，询问次数。

第二行 n(1≤n≤217) 个数，表示原序列。

接下来 m(1≤m≤100000) 行，每行三个数 l,r,xl,r,x 表示对区间[l,r][l,r] 加上 xx

Output

共 mm 行，表示查询的权值和。

Sample Input

8 2 
1 2 3 4 5 6 7 8
1 3 4
1 8 2

Sample Output

720
960

思路

区间修改，区间求和，但是这题不用写查询，因为从所有叶子节点到根节点的链的和为根节点的权值*(2*n-1)

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
#define ls 2*x
#define rs 2*x+1
long long a[N],tr[N<<2],lazy[N<<2];
void build(int x,int l,int r) {
	if(l==r) {
		tr[x]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[x]=tr[ls]+tr[rs];
}
void pushdown(int x,int len) {
	if(lazy[x]) {
		lazy[ls]+=lazy[x];
		lazy[rs]+=lazy[x];
		tr[ls]+=lazy[x]*len/2;
		tr[rs]+=lazy[x]*len/2;
		lazy[x]=0;
	}
}
void update(int x,int l,int r,int L,int R,int v) {
	if(l>=L&&r<=R) {
		lazy[x]+=v;
		tr[x]+=v*(r-l+1);
		return;
	}
	pushdown(x,r-l+1);
	int mid=(l+r)>>1;
	if(L<=mid)update(ls,l,mid,L,R,v);
	if(mid<R) update(rs,mid+1,r,L,R,v);
	tr[x]=tr[ls]+tr[rs];
}
signed main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%lld",&a[i]) ;
	build(1,1,n);
	while(m--) {
		long long l,r,v;
		scanf("%lld%lld%lld",&l,&r,&v);
		update(1,1,n,l,r,v);
		//cout<<tr[10]<<endl;
		printf("%lld\n",tr[1]*(1ll*n*2-1));
	}

	return 0;
}
/*8 2
1 2 3 4 5 6 7 8
1 8 2
1 3 4
*/