P3368 【模板】树状数组 2题解

· · 题解

应该不会有人先做模板 2 后做模板 1 吧？

默认读者已经完成了【模板】树状数组 1，所以本题解重点讲解差分部分。

前置知识

  1. 树状数组单点修改，区间查询。
  2. 差分思想。

    思路

    众所周知，树状数组是一种非常好写且高效的求前缀和的数据结构。普通的树状数组仅仅只支持单点修改。那么如果题目要求区间修改，单点查询，该怎么做呢？

    修改

    不难想到可以利用差分思想修改，即把树状数组看作差分数组。每次让区间 [l,r] 加上 v 时，只需要让下标为 l，l+\operatorname{lowbit}(l) 等处加上 v，让 r+1，r+1+\operatorname{lowbit}(r+1) 等处加上 -v 即可。

    查询

    查询第 i 个数的值时，正常查询到 i 的前缀和，便可以得出答案。

    正确性和复杂度分析

    这样为什么是正确的呢？

众所周知，只要对差分数组求一个前缀和，就可以还原出原数组。而树状数组就是用于求前缀和的数据结构。我们用构建差分数组的方式去构建树状数组，使得此时的树状数组同时具有差分数组和普通树状数组的性质。这样，求一遍前缀和便可以得出原数据。
仔细想想，这样做的本质就是用树状数组维护差分数组。

时间复杂度显然是 O(n\log{n})。

代码

代码与普通树状数组相差不大，唯一有区别的就是 do_add 函数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sta__[100], stalen;
inline ll read() {
    ll x = 0, f = 1;
    char ch;
    while ((ch = getchar()) < 48 || ch > 57)if (ch == '-')f = -1;
    while (ch >= 48 && ch <= 57)x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}
inline void write (ll x, bool bo) {
    if (x < 0)putchar ('-'), x = -x;
    do sta__[++stalen] = x % 10, x /= 10;
    while (x);
    while (stalen)putchar (sta__[stalen--] + 48);
    putchar (bo ? '\n' : ' ');
}
const ll N = 500009;
ll tr[N];
ll n, m;
inline ll lowbit (ll x) {
    return x & (-x);
}
inline void add (ll pos, ll v) {
    while (pos <= n) {
        tr[pos] += v;
        pos += lowbit (pos);
    }
}
inline void do_add (ll k, ll y, ll x) { //差分思想修改
    add (x, k);
    add (y + 1, -k);
}
inline ll do_qu (ll pos) {
    ll res = 0;
    while (pos > 0) {
        res += tr[pos];
        pos -= lowbit (pos);
    }
    return res;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        do_add (read(), i, i);
    for (int i = 1; i <= m; i++) {
        ll op = read();
        if (op == 1)do_add (read(), read(), read()); //函数传参从右到左
        else write (do_qu (read()), 1);
    }
    return 0;
}