C++ 区间和问题：高效算法及代码实现

问题描述

假设有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

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

样例 #1

样例输入 #1

3 3
1 2
3 6
7 5
1 3
4 6
7 8

样例输出 #1

8
0
5

提示

$−10^9≤x≤10^9 ,$

$1≤n,m≤10^5,$

$−10^9≤l≤r≤10^9,$

$−10000≤c≤10000$

代码实现

朴素解法

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<long long> nums(1000000001, 0);
    
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        nums[x] += c;
    }
    
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        long long sum = 0;
        for (int j = l; j <= r; j++) {
            sum += nums[j];
        }
        cout << sum << endl;
    }
    
    return 0;
}

优化：前缀和

我们可以使用前缀和来优化求区间和的过程。前缀和数组 sum 中，sum[i] 表示从下标 0 到下标 i 所有数的和。那么，区间 [l,r] 的和就可以用 sum[r] - sum[l-1] 计算。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<long long> nums(1000000001, 0);
    vector<long long> sum(1000000001, 0); // 前缀和数组
    
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        nums[x] += c;
    }
    
    // 计算前缀和
    sum[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        sum[i] = sum[i - 1] + nums[i];
    }
    
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        long long ans = sum[r] - sum[l - 1];
        cout << ans << endl;
    }
    
    return 0;
}

总结

本文讲解了如何用 C++ 解决区间和问题，并提供了两种解法：朴素解法和利用前缀和的优化解法。前缀和解法可以将时间复杂度从 O(nm) 降低到 O(n+m)，有效提高了程序效率。

希望本文能够帮助读者更好地理解和掌握区间和问题的解决方法。