高级前缀和

高级前缀和实现

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

题目

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

输入格式

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

输出格式

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

代码实现

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

#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

输入：

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

输出：

5
8

示例 2

输入：

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

输出：

6
9
10

示例 3

输入：

2 2
100 1
200 2
100 200
150 250

输出：

3
2

代码说明

输入处理：

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

离散化和前缀和实现：

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

主函数逻辑：

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

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

输入示例

假设输入如下：

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. 读取输入并存储操作：

   int m, n;
   cin >> m >> n;

   m = 3，n = 2。

   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)]。

   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. 离散化处理：

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

   对 alls 进行排序和去重。

   alls = [1, 2, 3]。

3. 执行添加操作：

   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. 构建前缀和数组：

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

   构建前缀和数组 s。

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

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。

最终输出

18 13

总结

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