小码匠的信息学江湖:【模板】树状数组 3 ：区间修改，区间查询

2023-09-19 08:19:51 浏览数 (1)

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

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

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

题目信息

  • https://loj.ac/p/132

参考资料

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

题目描述

这是一道模板题。

给定数列

a[1], a[2], dots, a[n]

，你需要依次进行 q 个操作，操作有两类：

  • 1 l r x：给定 l,r,x，对于所有
iin[l,r]

，将 a[i] 加上 x（换言之，将

a[l], a[l 1], dots, a[r]

分别加上 x）；

  • 2 l r：给定 l,r，求
sum_{i=l}^ra[i]

的值（换言之，求

a[l] a[l 1] dots a[r]

的值）。

输入格式

第一行包含 2 个正整数 n,q，表示数列长度和询问个数。保证

1le n,qle 10^6

。 第二行 n 个整数

a[1],a[2],dots,a[n]

，表示初始数列。保证

|a[i]|le 10^6

。 接下来 q 行，每行一个操作，为以下两种之一：

  • 1 l r x：对于所有
iin[l,r]

，将 a[i] 加上 x；

  • 2 l r：输出
sum_{i=l}^ra[i]

的值。

保证

1le lle rle n, |x|le 10^6

。

输出格式

对于每个 2 l r 操作，输出一行，每行有一个整数，表示所求的结果。

样例

输入复制

代码语言：javascript复制
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

输出复制

代码语言：javascript复制
15
34
32
33
50
数据范围与提示

对于所有数据，

1le n,qle 10^6, |a[i]|le 10^6, 1le lle rle n, |x|le 10^6

。

AC代码

代码语言：javascript复制
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl 'n';
typedef long long LL;

struct node {
    LL w, d;
};

struct FenwickTree{
    vector<LL> v;
    vector<node> 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("%lld", &v[i]);
        }
    }

    void initialize_2 () {
        for (int i = 1; i <= n;   i) {
            int x = i;
            while (x <= n) {
                c[x].w  = v[i] - v[i - 1];
                c[x].d  = (v[i] - v[i - 1]) * (i - 1);
                x  = lowbit(x);
            }
        }
    }

    node cnt (int a) {
        node ans = {0, 0};
        for(; a > 0; a -= lowbit(a)) {
            ans.w  = c[a].w;
            ans.d  = c[a].d;
        }
        return ans;
    }

    void add_3(int x, LL w) {
        int i = x;
        for (; x <= n; x  = lowbit(x)) {
            c[x].w  = w;
            c[x].d  = (i - 1) * w;
        }//区间修改 区间查询
    }

    LL ans(int l, int r) {
        return (r * cnt(r).w - cnt(r).d) - ((l - 1) * cnt(l - 1).w - cnt(l - 1).d);
        //区间修改 区间查询
    }
};

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 l, r;
            LL w;
            scanf("%d%d%lld", &l, &r, &w);
            ft.add_3(l, w);
            ft.add_3(r   1, -w);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lldn", ft.ans(l, r));
        }
    }
}

void happy_coder() {

}

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

    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // fclose(stdin);
    // fclose(stdout);

    return 0;
}
include int 数据 数组 效率

0 人点赞