看错题(赛氪冬季赛)【线段树】

传送门

给定一个能够满足是完全二叉树的线段树
能够在线段树上区间加值，每次询问求整棵树的价值
价值定义为 ∑ u ∑ w , w ∈ u ➡ 1 路 径 上 的 节 点 值 , u ∈ 线 段 树 叶 子 节 点 sum_u{sum{w},win u➡1路径上的节点值},u in线段树叶子节点 ∑u​∑w,w∈u➡1路径上的节点值,u∈线段树叶子节点

数据范围较大，需要在区间求和的过程中，动态维护其价值
一开始建树的时候，可以预先求出价值 a n s = ∑ u v a l u ∗ l e n u , u ∈ 所 有 线 段 树 节 点 ans=sum_u{val_u*len_u},u in所有线段树节点 ans=∑u​valu​∗lenu​,u∈所有线段树节点, v a l u val_u valu​表示节点的值， l e n u len_u lenu​表示当前节点掌控的区间大小（也就是拥有多少个叶子节点），这样能求出单个节点对于整颗树的贡献

对于区间加来说，不能一直将标记下放到每个叶子节点，时间复杂度不允许，所以在使用懒惰标记的同时还要维护子树的贡献，经过分析，如果对于此子树的叶子节点 + k +k +k的话，整颗子树造成的贡献 = ( 2 d e p u − 1 ) ∗ k ∗ l e n =({2^{dep_u}}-1)*k*len =(2depu​−1)∗k∗len，细心画图可以发现，对于叶子节点到此节点的路径是 1 k − 2 k − 4 k − 8 k − . . . 1k-2k-4k-8k-... 1k−2k−4k−8k−...形式的，所以可以通过深度求出每条链的贡献，有多少链呢？也就是叶子节点的个数了 = l e n =len =len。因此能动态维护价值。

//L

#include 
using namespace std;
#define sc scanf
#define pr printf
#define ll long long
#define int long long
#define FILE_OUT freopen("out", "w", stdout);
#define FILE_IN freopen("in", "r", stdin);
#define debug(x) cout << #x << ": " << x << "n";
#define CIN(arr) for (int i = 1; i <= N; ++i) cin >> arr[i];
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define MAX(a, b) (a >= b ? a : a = b)
#define MIN(a, b) (a <= b ? a : a = b)
#define AC 0
#define WA 1
#define INF 0x3f3f3f3f
const ll MAX_N = 1e6+5;
const ll MOD = 1e9+7;
int N, M, K;

int tr[MAX_N];
int lazy[MAX_N];
int arr[MAX_N];
int dep[MAX_N];

int ans = 0;

void build(int rt, int l, int r) {
	if (l == r) {
		tr[rt] = arr[l];
		ans += arr[l];
		dep[rt] = 1;
		return;
	}
	int mid = l + ((r-l)>>1);
	build(rt<<1, l, mid);
	build(rt<<1|1, mid+1, r);
	tr[rt] = tr[rt<<1] + tr[rt<<1|1];
	dep[rt] = dep[rt<<1] + 1;
	ans += tr[rt] * (r - l + 1);
}

void push_down(int rt, int l, int r) {
	if (!lazy[rt]) return;
	int mid = l + ((r-l)>>1);
	tr[rt<<1] += lazy[rt] * (mid - l + 1);
	tr[rt<<1|1] += lazy[rt] * (r - mid);
	lazy[rt<<1] += lazy[rt];
    lazy[rt<<1|1] += lazy[rt];
	lazy[rt] = 0;
}

void update(int rt, int l, int r, int x, int y, int k) {
	if (x <= l && r <= y) {
		tr[rt] += (r - l + 1) * k;
		lazy[rt] += k;
		ans += ((1ll<>1);
	if (x <= mid) update(rt<<1, l, mid, x, y, k);
	if (y  > mid) update(rt<<1|1, mid+1, r, x, y, k);
	tr[rt] = tr[rt<<1] + tr[rt<<1|1];
	ans += tr[rt] * (r - l + 1);
}

void solve() {
    cin >> N >> M;
    CIN(arr);
    build(1,1,N);
    
	int l, r, v;
	for (int _ = 1; _ <= M; ++_) {
		cin >> l >> r >> v;
		update(1, 1, N, l, r, v);
		cout << ans << "n";
	}
}

signed main() {
	#ifndef ONLINE_JUDGE
//	FILE_IN
	FILE_OUT
	#endif
	int T = 1;//cin >> T;
	while (T--) solve();

	return AC;
}