【推荐】小码匠的信息学江湖:【模板】树状数组 2

小码匠

发布于 2023-09-09 10:20:00

2070

发布于 2023-09-09 10:20:00

文章被收录于专栏：小码匠和老码农

大家好！我是小码匠。

这是我的信息学江湖，这里没有九阴白骨爪，也没有降龙十八掌。

但是，老码农的打狗棒舞的是熠熠生辉，代码敲不好，他就要给我展示打狗棒法了。

本系列是模版系列，会整理

题目链接地址
参考资料
AC代码
自己挖坑（部分题目有）

关于思路大家可参照题目信息的链接地址或者相关书籍，文章旨在分享代码。

题目信息

https://www.luogu.com.cn/problem/P3368
- 题解：https://www.luogu.com.cn/problem/solution/P3368

参考资料

树状数组
- https://oi-wiki.org/ds/fenwick/

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 x；
求出某一个数的值。

输入格式

第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含 N 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 M 行每行包含 2 或 4个整数，表示一个操作，具体如下：

操作 1：格式：1 x y k 含义：将区间[x,y] 内每个数加上 k；

操作 2：格式：2 x 含义：输出第 x 个数的值。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

输出 #1复制

6
10

说明/提示

样例 1 解释：

img

故输出结果为 6、10。

数据规模与约定

对于 30% 的数据：N≤8，M≤10；

对于 70% 的数据：N≤10000，M≤10000；

对于 100% 的数据：1≤N,M≤500000，1≤x,y≤n，保证任意时刻序列中任意元素的绝对值都不大于 230。

AC代码

#include <bits/stdc++.h>
using namespace std;

struct FenwickTree{
    vector<int> v;
    vector<int> c;
    int n;
    FenwickTree (int l):
                         n(l), c(l + 1), v(l + 1){}

    int lowbit (int a) {
        return (-a) & a;
    }

    void read() {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &v[i]);
        }
    }

    void initialize_1 () {
        for (int i = 1; i <= n; ++i) {
            c[i] += v[i];
            if (i + lowbit(i) <= n) {
                c[i + lowbit(i)] += c[i];
            }
        }
    }

    void initialize_2 () {
        for (int i = 1; i <= n; ++i) {
            c[i] += v[i] - v[i - 1];
            if (i + lowbit(i) <= n) {
                c[i + lowbit(i)] += c[i];
            }
        }
    }

    int cnt (int a) {
        int ans = 0;
        for(; a > 0; a -= lowbit(a)) {
            ans += c[a];
        }
        return ans;
    }

    void add (int a, int b){
        for (; a <= n; a += lowbit(a)) {
            c[a] += b;
        }
    }

    int sum (int a, int b){
        return cnt(b) - cnt(a - 1);
    }
};

void best_coder() {
    int n, m;
    scanf ("%d%d", &n, &m);
    FenwickTree ft(n);
    ft.read();
    ft.initialize_2();
    for (int i = 0; i < m; ++i) {
        int a;
        scanf("%d", &a);
        if (a == 1) {
            int b, c, d;
            scanf("%d%d%d", &b, &c, &d);
            ft.add(b, d);
            ft.add(c + 1, -d);
        } else {
            int b;
            scanf("%d", &b);
            printf("%d\n", ft.cnt(b));
        }
    }
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除

int