高级前缀和实现

在处理大范围坐标的区间求和时，可以使用离散化技术和前缀和结合来提高效率。本文将介绍如何使用C++实现这一方法。

题目

假定有一个无限长的数轴，数轴上每个坐标都是0。
现在，我们首先进行n次操作，每次操作将某一位置x上的数加c。
接下来，进行m次询问，每个询问包含两个整数l和r，你需要求出在区间[l,r]之间所有数的和。

输入格式

第一行包含两个整数n、m。
接下来n行，每行包括两个整数x和c。
再接下来里m行，每行包括两个整数l和r。

输出格式

共m行，每行输入一个询问中所求得区间内数字和。

代码实现

以下是一个实现高级前缀和的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include<iostream>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include<vector>
#include<algorithm>
typedef pair<int,int> PII; 
const int N=300010;
int a[N]; // 离散化后的数组，用于存储离散化坐标对应的值
int s[N]; // 前缀和数组，用于快速查询区间和
vector<int> alls; // 用于存储所有需要离散化的坐标
vector<PII> add, question; // add存储添加操作，question存储查询操作

int find(int x) // 二分查找函数，找到x在alls中的位置（离散化后的坐标）
{
    int l=0, r=alls.size()-1;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 返回离散化后的坐标索引
}

int main()
{ 
    ios; // 优化输入输出
    int m, n;
    cin >> m >> n; // 读取操作的数量，m是添加操作的数量，n是查询操作的数量

    // 读取添加操作
    for(int i = 0; i < m; i++)
    {
        int b, c;
        cin >> b >> c; // 读取添加操作的坐标和值
        alls.push_back(b); // 将坐标存入alls中
        add.push_back({b, c}); // 将操作存入add中
    }
    
    // 读取查询操作
    for(int i = 0; i < n; i++)
    {
        int b, c;
        cin >> b >> c; // 读取查询操作的区间起点和终点
        alls.push_back(b); // 将查询区间的两个坐标都存入alls中
        alls.push_back(c);
        question.push_back({b, c}); // 将查询操作存入question中
    }

    // 离散化：对所有的坐标进行排序，并去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 离散化并执行添加操作
    for(auto x : add)
    {
        int h = find(x.first); // 找到离散化后的坐标索引
        a[h] += x.second; // 在离散化后的数组中进行添加操作
    }

    // 构造前缀和数组
    for(int i = 1; i <= alls.size(); i++) 
        s[i] = s[i - 1] + a[i];

    // 处理查询操作
    for(auto x : question)
    {
        int h = find(x.first); // 找到查询区间起点的离散化坐标
        int t = find(x.second); // 找到查询区间终点的离散化坐标
        cout << s[t] - s[h - 1] << ""; // 输出查询结果，即区间和
    }
    
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
2
3
4
5
6

3 2
1 2
2 3
4 5
1 2
2 4

1
2

5
8

示例 2

输入：

1
2
3
4
5
6
7
8

4 3
1 1
2 2
3 3
4 4
1 3
2 4
1 4

1
2
3

6
9
10

示例 3

输入：

1
2
3
4
5

2 2
100 1
200 2
100 200
150 250

1
2

3
2

代码说明

输入处理：

• 使用 cin 函数读取操作数 m 和查询数 n。
• 读取操作和查询的坐标，存储在对应的向量中，并记录所有需要的坐标。

离散化和前缀和实现：

• 通过排序和去重对坐标进行离散化。
• 使用离散化后的坐标构造前缀和数组。

主函数逻辑：

• 读取输入数据并进行离散化处理。
• 构造前缀和数组，并处理每个查询，输出对应的区间和。

当然可以。下面是一个具体的例子以及按照代码处理流程的解释：

输入示例

假设输入如下：

1
2
3
4
5
6

3 2
1 5
2 6
3 7
1 3
2 3

输入解释

• 第1行：3 2 表示有3个添加操作和2个查询操作。
• 第2-4行：1 5，2 6，3 7 是3个添加操作，表示在坐标1加上5，在坐标2加上6，在坐标3加上7。
• 第5-6行：1 3，2 3 是2个查询操作，分别查询区间 [1, 3] 和 [2, 3] 的和。

按照代码处理流程

1. 读取输入并存储操作：

   1 2	int m, n; cin >> m >> n;

   m = 3，n = 2。

   1 2 3 4 5 6

   for (int i = 0; i < m; i++) { int b, c; cin >> b >> c; alls.push_back(b); add.push_back({b, c}); }

   处理添加操作，将坐标 b 存入 alls，并将操作 (b, c) 存入 add。

   alls = [1, 2, 3]，
   add = [(1, 5), (2, 6), (3, 7)]。

   1 2 3 4 5 6 7

   for (int i = 0; i < n; i++) { int b, c; cin >> b >> c; alls.push_back(b); alls.push_back(c); question.push_back({b, c}); }

   处理查询操作，将区间起点和终点 b, c 存入 alls，并将操作 (b, c) 存入 question。

   alls = [1, 2, 3, 1, 3, 2, 3]，
   question = [(1, 3), (2, 3)]。

2. 离散化处理：

   1 2	sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());

   对 alls 进行排序和去重。

   alls = [1, 2, 3]。

3. 执行添加操作：

   1 2 3 4

   for (auto x : add) { int h = find(x.first); a[h] += x.second; }

   将添加操作应用到离散化后的数组 a 中。

   find(1) = 1，find(2) = 2，find(3) = 3。

   更新后 a 数组的变化：
   a = [0, 5, 6, 7]。

4. 构建前缀和数组：

   1 2	for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

   构建前缀和数组 s。

   前缀和数组 s：
   s = [0, 5, 11, 18]。

5. 处理查询操作并输出结果：

   1 2 3 4 5

   for (auto x : question) { int h = find(x.first); int t = find(x.second); cout << s[t] - s[h - 1] << " "; }

   处理查询操作并输出结果。

   • 查询区间 [1, 3]：
     find(1) = 1，find(3) = 3，
     结果：s[3] - s[0] = 18 - 0 = 18。
   • 查询区间 [2, 3]：
     find(2) = 2，find(3) = 3，
     结果：s[3] - s[1] = 18 - 5 = 13。

最终输出

1

18 13

总结

通过这个例子，我们可以看到代码是如何处理添加和查询操作的。代码通过离散化技术将原始坐标映射到较小的连续整数范围，从而在固定大小的数组上执行操作，这显著提高了处理效率。

前缀和实现

在处理数组区间求和时，可以使用前缀和技术来提高效率。本文将介绍如何使用C++实现前缀和。

代码实现

以下是一个实现前缀和的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>

using namespace std;

#define N 100010

long long f[N];
int n, m, t, x, y;

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &t);
        f[i] = f[i - 1] + t;
    }   

    while(m--) {
        scanf("%d %d", &x, &y);
        printf("%lld", f[y] - f[x - 1]);
    }
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
2
3
4
5

5 3
1 2 3 4 5
1 3
2 4
1 5

1
2
3

6
9
15

示例 2

输入：

1
2
3
4

6 2
1 1 1 1 1 1
1 6
3 5

1
2

6
3

示例 3

输入：

1
2
3

4 1
10 20 30 40
2 3

1

50

代码说明

输入处理：

• 使用 scanf 函数读取数组长度 n 和查询次数 m。
• 读取数组元素，并计算前缀和存储在数组 f 中。

前缀和实现：

• 通过累加前缀和数组 f，使 f[i] 表示前 i 个元素的和。
• 对于每个查询，计算并输出区间和 f[y] - f[x - 1]。

主函数逻辑：

• 读取输入数据并计算前缀和数组。
• 处理每个查询，输出对应的区间和。