题解：P13976 数列分块入门 1

chenyuan3 · 2025-09-13 10:48:43 · 题解

:::info[题意简述]

原题链接。

:::

分块简介

分块，顾名思义，把数组分成一块一块的。确定块长（即每块的元素个数）s 后，就可以把 a 数组分成这样：（n 表示数组长度）

• 第 1 块：a_1,a_2,a_3,...,a_s；
• 第 2 块：a_{s+1},a_{s+2},a_{s+3},...,a_{2s}；
• 第 3 块：a_{2s+1},a_{2s+2},a_{2s+3}...,a_{3s}；
• 以此类推，第 i 块：a_{s(i-1)+1},a_{s(i-1)+2},a_{s(i-1)+3},...,a_{si}；
• 最后一块，即第 \lceil\frac ns\rceil 块：a_{\lceil\frac ns\rceil s+1},a_{\lceil\frac ns\rceil s+2},a_{\lceil\frac ns\rceil s+3},...,a_n（由于 n 很有可能不是 s 的倍数，因此最后一块的元素个数可能不到 s 个）。

分好后，就可以进行区间和统计、类似线段树的懒标记。

对于本题，不需要区间和统计，懒标记可以存储整个块都要加的一个数。

时间复杂度分析以及块长的选择

设总长 n，块长 s。显然可以 O(1) 获取一个元素对应块的编号，因此查询操作可以 O(1) 解决。

修改操作分为三个部分：整块之前、整块、整块之后。

• 整块之前：可以使用懒标记进行整体操作的块的前面。可能有刚好 s-1 个元素需要进行操作（再多就可以整块操作了），复杂度 O(s)；
• 整块：可以使用懒标记进行整体操作的块。可能会对所有块进行整块操作，复杂度 O(\frac ns)；
• 整块之后：类似于整块之前，复杂度 O(s)。

综上，修改操作时间复杂度为 O(s+\frac ns)，如果 s 太小或者太大都会导致总复杂度变高，通过数学直觉或者图像可以发现当 s=\frac ns 即 s=\sqrt n 时复杂度最小，为 O(\sqrt n)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 3e5 + 10, maxs = 550; // 550 >= sqrt(maxn)
ll n, a[maxn], siz, tag[maxs], opt, l, r, c; // siz: 块长, tag: 懒标记
void solve()
{
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    siz = sqrt(n);
    for (ll q = 1; q <= n; q++)
    {
        cin >> opt >> l >> r >> c;
        if (opt)
        {
            cout << a[r] + tag[(r - 1) / siz + 1] << endl; // 记得加上懒标记
        }
        else
        {
            for (; l <= r && l % siz != 1; l++)
            {
                a[l] += c;
            } // 整块之前
            for (; l <= r - siz; l += siz)
            {
                tag[(l - 1) / siz + 1] += c;
            } // 整块
            for (; l <= r; l++)
            {
                a[l] += c;
            } // 整块之后
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}