Description：

给一棵维护区间和的线段树，支持区间加，询问每次随机进入某棵子树整条路经的权值和。

$1\leqslant n \leqslant 10^6$

Solution：

一个显然的思路是按题意维护一棵线段树，树上再维护一个期望这样做是 $O(n\log n)$ 的。

其实发现修改单个位置的值会把它到根的路径权值都加 $x$ ，设这个叶子深度为 $dep[i]$ ，那么这个单点修改会对答案造成的影响为 $\begin{align}\sum_{k=1}^{dep[i]}(\frac 1 2)^x\times k=(2-(\frac 1 2)^{dep[i]})\times k\end{align}$ ，所以维护一个 $(\frac 1 2)^{dep[i]}$ 前缀和区间整体操作即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

    register ll res = 0,f = 1;

    register char c = getchar();

    while(!isdigit(c))

    {

        f = (c == '-' ? -1 : 1);

        c = getchar();

    }

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

ll n,m,k;

#define MAXN 1000010

ll dep[MAXN];

long double sum_dep[MAXN];

ll power[30];

void getdep(int l,int r,int d)

{

    if(l == r)

    {

        dep[l] = d;

        return;

    }

    register int mid = ((l + r) >> 1);

    getdep(l,mid,d + 1);

    getdep(mid + 1,r,d + 1);

    return;

}

int main()

{

    n = read();m = read();k = read();

    getdep(1,n,0);

    register long double ans = 0;

    power[0] = 1;

    for(register int i = 1;i <= 29;++i)power[i] = power[i - 1] * 2;

    for(register int i = 1;i <= n;++i)

    {

        ans += (long double)read() * k * (2 - 1.0 / power[dep[i]]);

    }

    for(register int i = 1;i <= n;++i)sum_dep[i] = 1.0 / power[dep[i]] + sum_dep[i - 1];

    register ll l,r,x;

    for(register int i = 1;i <= m;++i)

    {

        l = read();r = read();x = read();

        ans += ((r - l + 1) * 2 - (sum_dep[r] - sum_dep[l - 1])) * x * k;

        x = ans;

        printf("%lld\n",x);

    }

    return 0;

}