Catshao

用户名：Catshao

访问量：25541

签　名：

stO KHIN Orz

等　　级
排　　名	172
经　　验	6744
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

人类智慧分块
浏览：160

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

值域分块题解

　　作者: Catshao　　　　发表时间：2022-02-15 14:41:23 浏览：172　|　评论：0　

原题链接：值域分块

这个有什么用：[[Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 。

O(1) 区间求和，考虑维护前缀和。使用树状数组做显然是 log 的，于是考虑值域分块。

维护两个信息：以块为单位的前缀和，块内前缀和。

放下代码

```cpp
//
// Created by Cat-shao on 2022/2/15.
//

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

const int MAX_N = 100010;

class block {
public:
    static const int MAX_LEN = 320;
    int b[MAX_N], pre[MAX_LEN], pre2[MAX_N], n, len;

block(int _n) {
        n = _n;
        len = sqrt(n);
        for (int i = 1; i <= n; ++i) {
            b[i] = (i - 1) / len + 1;
        }
        memset(pre, 0, sizeof(pre));
        memset(pre2, 0, sizeof(pre2));
    }

void add(int x, int v) {
        for (int i = x; i <= min(n, b[x] * len); ++i) {
            pre2[i] += v;
        }
        for (int i = b[x]; i <= b[n]; ++i) {
            pre[i] += v;
        }
    }

int sum(int l, int r) {
        return pre[b[r] - 1] + pre2[r] - pre[b[l - 1] - 1] - pre2[l - 1];
    }
};

namespace naive {
    int n, m, a[MAX_N];
    void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> n >> m;
        int op, x, y;
        for (int i = 1; i <= m; ++i) {
            cin >> op >> x >> y;
            if (op == 1) {
                a[x] += y;
            } else {
                cout << accumulate(a + x, a + y + 1, 0) << '\n';
            }
        }
    }
}

namespace test {
    void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n, m, op, l, r;
        cin >> n >> m;
        block b(n);
        for (int i = 1; i <= m; ++i) {
            cin >> op >> l >> r;
            if (op == 1) {
                b.add(l, r);
            } else {
                cout << b.sum(l, r) << '\n';
            }
        }
    }
}

int main()
{
    test::main();
    return 0;
}
```

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

Catshao

TA的其他文章

你可能喜欢

不同单词个数统计（C语言代码）

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

值域分块题解

评论区

精彩推荐

C语言训练-求素数问题（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言考试练习题_保留字母（C语言代码）

P1002 （C语言代码）

矩阵乘法（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

WU-整数平均值（C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

不同单词个数统计 （C语言代码）

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

值域分块题解

评论区

精彩推荐

C语言训练-求素数问题 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言考试练习题_保留字母 （C语言代码）

P1002 （C语言代码）

矩阵乘法 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

WU-整数平均值 （C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

不同单词个数统计（C语言代码）

　　评论区

C语言训练-求素数问题（C语言代码）

C语言考试练习题_保留字母（C语言代码）

矩阵乘法（C++代码）

WU-整数平均值（C++代码）