109徐守佳

用户名：dotcpp0787174

访问量：995

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	919
经　　验	3474
参赛次数	1
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[蓝桥杯2022年第十三届决赛真题-最大数字] 贪心+dfs
浏览：57

题可以贪心做，人要看准了爱.
浏览：54

[信息学奥赛一本通T1541-数列区间最大值] ST表
浏览：21

你可能喜欢

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

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

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

[信息学奥赛一本通T1547-区间和]-分块写法

　　作者: 109徐守佳　　　　发表时间：2024-10-29 21:45:51 浏览：15　|　评论：0　

原题链接：信息学奥赛一本通T1547-区间和

# 基于**分块思想**的区间查询与单点修改问题

##  一、题目分析
题目要求实现两个操作：
1. 单点修改：将数组中某个元素增加一个值。
2. 区间查询：查询数组中某个区间的元素和。
由于数据规模较大，直接使用暴力解法会导致超时。
因此，我们需要采用一种高效的算法来解决这个问题。

##  二、算法思路
本题采用分块算法，将数组划分为若干块，每块大小为 sqrt(n)。这样可以在保证查询和修改操作效率的同时，降低空间复杂度。
1. 分块处理
将数组划分为若干块，每块大小为 sqrt(n)。这样可以使得每个块内的元素个数尽可能接近，便于后续操作。
2. 单点修改
当进行单点修改操作时，直接更新对应元素的值，并维护所在块的元素和。
3. 区间查询
当进行区间查询操作时，分为以下三种情况：
   a. 当查询区间完全位于一个块内时，直接暴力计算区间和。
   b. 当查询区间跨越多个块时，分别计算左端块、中间完整块和右端块的区间和，然后相加。
   c. 当查询区间恰好为一个块时，直接返回该块的元素和。
## 三、代码实现
以下是代码实现的关键步骤：
1. 初始化块信息
```cpp
len = sqrt(n);
for(int i=1;i<=n;i++) id[i] = (i-1) / len + 1;
```
2. 单点修改
```cpp
void modify(int x, int c) {
    int tid = id[x];
    a[x] += c;
    s[tid] += c;
}
```
3. 区间查询
```cpp
int query(int l, int r) {
    int sid = id[l], eid = id[r];
    int res = 0;
    if (sid == eid) {
        for (int i = l; i <= r; i++) res += a[i] + b[sid];
        return res;
    }
    // 计算左端块和右端块的区间和
    // 计算中间完整块的区间和
    // 返回最终结果
}
```
## 四、代码

```cpp
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ULL unsigned long long
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int id[N],a[N],b[N],len,s[N];
void modify(int x,int c)
{
    int tid = id[x];
    a[x] += c;
    s[tid] += c;
}
int query(int l,int r)
{
    int sid = id[l] , eid = id[r];
    int res = 0;
    if(sid == eid)
    {
        for(int i=l;i<=r;i++) res = (res + a[i] + b[sid]);
        return res;
    }

for(int i=l;id[i]==sid;i++) res = (res + a[i] + b[sid]);
    for(int i=sid+1;i<eid;i++) res = (res + s[i]);
    for(int i=r;id[i]==eid;i--) res = (res + a[i] + b[eid]);
    return res;
}
void solve()
{
    cin >> n >> m;
    len = sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (i-1) / len + 1;

while(m--)
    {
        int op,a,b;
        cin >> op >> a >> b;
        if(op == 0) modify(a,b);
        else cout << query(a,b)<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.28 13:08:13
 */
```

## 五、复杂度分析
单点修改的时间复杂度为 O(1)，区间查询的时间复杂度为 O(sqrt(n))。

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

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

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

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

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

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

[信息学奥赛一本通T1547-区间和]-分块写法

评论区

精彩推荐

回文串（C语言代码）

C语言训练-求PI* （C语言代码）

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

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

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

回文数字（C语言代码）

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

矩阵乘方（C语言代码）

输出九九乘法表（C语言代码）

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

109徐守佳

TA的其他文章

你可能喜欢

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

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

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

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

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

[信息学奥赛一本通T1547-区间和]-分块写法

评论区

精彩推荐

回文串 （C语言代码）

C语言训练-求PI* （C语言代码）

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

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

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

回文数字 （C语言代码）

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

矩阵乘方 （C语言代码）

输出九九乘法表 （C语言代码）

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

　　评论区

回文串（C语言代码）

回文数字（C语言代码）

矩阵乘方（C语言代码）

输出九九乘法表（C语言代码）