如何计算区间和问题中的？

19.Acwing基础课第802题-简单-区间和 题目描述 假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。 现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。 接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行，每行包含两个整数 x 和 c。 再接下来 m 行，每行包含两个整数 l 和 r。 输出格式 共 m 行，每行输出一个询问中所求的区间内数字和。 数据范围 −109≤x≤109 1≤n,m≤100000， −109≤li≤ri≤109 −10000≤c≤10000 输入样例： 3 3 1 2 3 6 7 5 1 3 4 6 7 8 输出样例： 8 0 5 代码： #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010;//开30万是因为插入操作总数是10万（插入操作里1个坐标），查询操作是10万（查询操作两个坐标） int n, m; int a[N], s[N];//数组a[N]为新映射下标对应的数，s[N]为前缀和 vector<int> alls;//alls保存所要操作的下标 vector<PII> add, query;//add存插入的值，query用来存将来要查询的左右边界的离散化前的下标 //求x的值离散化后的结果 int find(int x)//二分法 { 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;//把数值映射到从1开始的数组里 } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({ x, c });//下标x的位置加c alls.push_back(x);//下标x离散化，先把x加到待离散化的数组里面去 } for (int i = 0; i < m; i++)//读入所有区间的左右端点 { int l, r; cin >> l >> r; query.push_back({ l, r }); alls.push_back(l);//读入所有区间的左右端点加到待离散化的数组里去 alls.push_back(r); } // alls数组去重 sort(alls.begin(), alls.end()); //删除所有重复元素，所有不重复元素放到数组前面去，返回新数组的最后一个数的位置 alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 处理插入 for (auto item : add) { int x = find(item.first); a[x] += item.second; } // 预处理前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];//alls.size()是用到的最大的坐标 // 处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second);//左右端点离散化后的值 cout << s[r] - s[l - 1] << endl;//中间所有数的个数是离散化后的区间的长度 } return 0; } alls作用 这段代码主要实现了对一个序列的两类操作：插入操作和区间查询操作。在实际的数组中可能只涉及到一个小部分下标，所以使用“离散化”可以高效地处理问题，即将实际用到的下标映射到连续的1,2,3...。这样可以避免使用一个非常大的数组。 alls 这个数组就是为了进行这个“离散化”操作而存在的。它用来收集所有可能涉及到的下标，然后对这些下标进行排序和去重，最后得到一个连续的下标列表。 在详细解释alls的作用之前，我们需要了解“离散化”的目的： 减少空间消耗：考虑到最大下标可能非常大，但实际上你只对一小部分下标进行了操作。离散化能将这些操作的下标映射到1,2,3...，这样你只需为实际操作的下标分配空间，而不是整个范围。 简化操作：对于某些算法，使用连续下标会更加简单高效。 现在来看alls的具体使用： 对于每一个插入操作，你需要知道在哪个位置插入（下标x），所以x被放入了alls数组中。 对于每一个查询操作，你需要知道查询的范围是哪些，即从哪个下标开始到哪个下标结束。所以l和r都被放入了alls数组中。 在收集完所有的下标后，使用sort和unique对alls数组进行排序和去重。这样你就得到了所有实际操作涉及到的下标的列表，而且是按顺序排列的。 当你需要对原数组的某个位置（比如x）进行操作时，先找到x在alls数组中的位置，这个位置就是x在离散化后的数组中的下标。 回到你的疑问，为什么alls中既有l也有r： 对于插入操作，你只关心在哪个位置插入，所以只需要x。 对于查询操作，你需要知道查询的开始和结束位置，所以你需要两个下标：l和r。这也是为什么在读取查询操作时，alls中既加入了l也加入了r。 这种离散化的技巧在处理涉及到大范围下标，但实际操作的下标数量较少的问题时非常有用。 query作用 在给出的代码中，query 是一个向量，其元素是整数对 (pair of integers)，用来存储区间查询操作的开始位置和结束位置。 在这个上下文中，一个查询操作可能是：查询从位置 l 到位置 r 的数值之和。对于每一个查询操作，这段代码都会读取两个整数 l 和 r，然后将它们作为一个整数对存储在 query 向量中。 举一个例子，假如有以下查询： 查询1：从位置3到位置5 查询2：从位置10到位置15 那么query向量将会是： { {3,5}, {10,15} } 在代码的后面部分，它会遍历 query 向量，然后对每一个查询计算从 l 到 r 的数值之和（经过离散化处理后的位置），并输出结果。 所以，query 的作用就是存储所有待处理的区间查询操作。 add作用 在提供的代码中，add 是一个类型为 vector<PII> 的向量，其中 PII 是 pair<int, int> 的类型别名，用于表示两个整数的对子 (pair)。 add 向量的作用是存储所有的插入操作的信息。具体地说，每当从输入中读取一个插入操作（指定在某个位置 x 增加一个值 c），这个操作的信息就被作为一个整数对 {x, c} 存储到 add 向量中。 例如，考虑以下插入操作： 操作1：在位置2加上值5 操作2：在位置4加上值3 那么 add 向量会是这样的： { {2,5}, {4,3} } 在后续的代码中，这个向量被用于更新主数据数组，即对每个 {x, c} 对，在离散化后的位置 x 上加上值 c。 总之，add 的主要作用是存储所有的插入操作信息，以便后续对数据进行更新。 为什么是for (int i = 1; i <= alls.size(); i++) 而不是for (int i = 1; i <=add.size(); i++) 在这段代码中，预处理的目标是计算数组 a 的前缀和并存储在数组 s 中。这样在后续处理区间查询时可以更快地得到结果。 考虑以下代码片段： // 预处理前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; 这里使用 alls.size() 而不是 add.size() 的原因在于，alls 向量不仅包含了通过插入操作获得的所有唯一下标，而且还包含了所有区间查询操作的开始和结束位置。因此，alls.size() 可能会大于 add.size()。 为什么我们关心所有的下标，包括那些仅仅在查询中出现的下标？ 答案是：为了确保我们的前缀和数组 s 覆盖了所有可能的查询范围。即使某些位置在 a 中为0，我们仍然需要这些位置在 s 中有对应的前缀和值，这样在执行区间查询时才能确保正确性。 例如，考虑下面的情况： 插入操作： x = 3, c = 5 查询操作： l = 1, r = 10 在这里，add.size() 是1，但是 alls.size() 是3（因为有 x, l 和 r）。如果我们只根据 add.size() 计算前缀和，那么 s 只会包含前1个元素的前缀和，这显然是不够的，因为我们的查询范围是从1到10。所以，我们需要确保 s 覆盖了所有在 alls 中的下标，这样无论查询的范围如何，我们都可以快速地得到答案。