摘要
Title: 第三届adpc冬季赛 L. 看错题
Tag: 树状数组
Memory Limit: 256 MB
Time Limit: 1000 ms

L. 看错题

题意

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

由于数据是满二叉树，所以把每个叶子节点选择一遍后的总和是固定的，也就是求 $x * sum$ ，其中 $x=2 ^ {log2(n) + 1} - 1$ ，由于要动态更新区间，并求和，可以采用区间修改+区间查询的树状数组

这里记录一下区间修改+区间查询的树状数组

在这个任务中，我们需要解决以下问题：
- 将一个区间内的值添加同样的数值
- 查询一个区间的和
定义差分数组 $c$ ,如果我们想求解一个 $S=A[1:n]$ 前缀和的话，有：

$\begin{aligned} S &= A[1] + A[2] + ... + A[n] \\ &= C[1] + (C[1] + C[2]) +...+(C[1]+C[2]+...+C[n]) \\ &= n * C[1] +(n - 1)*C[2] +...+1*C[n] \\ &= (n + 1)*(C[1] + C[2]+...+C[n]) - (1*C[1]+2*C[2]+...+n*C[n]) \end{aligned}$

因此我们可以使用另一个辅助数组 $d$ 来维护 $d[i] = c[i]*i$ 的值即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-03-27 11:03:59
* @FilePath: \ACM\Contest\i.cpp
* @LastEditTime: 2022-03-27 11:23:04
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define int LL
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
#define lowbit(x) x & -x

const int N = 2e5 + 10;
int tr[N], a[N], c[N];

void add(int x, int d)
{
    for (int i = x; i < N; i += lowbit(i))
    {
        tr[i] += d;
        c[i] += x * d;
    }
}
int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += (x + 1) * tr[i] - c[i];
    return res;
}

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], add(i, a[i] - a[i - 1]);
    int ceng = pow(2, log2(n) + 1) - 1;
    for (int i = 1; i <= m; i++)
    {
        int l, r, d;
        cin >> l >> r >> d;
        add(l, d), add(r + 1, -d);
        cout << ceng * (query(n) - query(0)) << '\n';
    }
    return 0;
}

L. 看错题

题意

思路

代码