题解：P13976 数列分块入门 1

· · 题解

P13976 数列分块入门 1

原来洛谷也有出分块系列的一天。

问题分析

本题要求实现一个支持区间加法和单点查询的数据结构。\ 给定一个长度为 n 的数列，需要处理两种操作：

  1. 区间加法：将第 l 到第 r 个数都加上 c。
  2. 单点查询：查询第 r 个数的值。

    算法选择

    直接暴力解法的时间复杂度是 O(n)，在数据量大时效率低下。

所以说我们采用‌分块算法‌来优化：

  1. 将数列分成 \sqrt{n} 个块，每块大小约为 \sqrt{n}。

  2. 区间操作时：

    • 完整块：使用延迟标记记录加法操作；
    • 不完整块：直接暴力修改元素值。

  3. 查询时：元素值 = 原始值 + 所在块的延迟标记。

AC Code


#include <iostream>
#include <cmath>
#define MX 300010
using namespace std;

int bs, n;
long long a[MX], b_add[MX];
int b_st[MX], b_cnt;

void init() {
    bs = sqrt(n);
    for(int i=0; i<n; i+=bs) {
        b_st[b_cnt++] = i;
    }
}

void add(int l, int r, long long c) {
    int bl = l/bs;
    int br = r/bs;

    if(bl == br) {
        for(int i=l; i<=r; i++) a[i] += c;
    } else {
        // 处理左边不完整块
        for(int i=l; i<(bl+1)*bs; i++) a[i] += c;
        // 处理中间完整块
        for(int i=bl+1; i<br; i++) b_add[i] += c;
        // 处理右边不完整块
        for(int i=br*bs; i<=r; i++) a[i] += c;
    }
}

long long qry(int r) {
    return a[r] + b_add[r/bs];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    init();

    for(int i=0; i<n; i++) cin >> a[i];

    for(int i=0; i<n; i++) {
        int op, l, r;
        long long c;
        cin >> op >> l >> r >> c;
        if(op == 0) {
            add(l-1, r-1, c);
        } else {
            cout << qry(r-1) << "\n";
        }
    }

    return 0;
}

::::info[提示：如果还是不懂，可以看一下代码实现过程]

  1. 分块初始化‌：计算块大小，记录每个块的起始位置。
  2. 区间加法：
    • 同块时直接遍历修改；
    • 跨块时分三部分处理：左不完整块、中间完整块、右不完整块。
  3. 单点查询‌：返回元素值加上所在块的延迟标记。