Consider an infinite linear axis where every integer coordinate holds an initial value of zero. The task involves processing $n$ point increment operations followed by anwsering $m$ range sum queries.

Given that coordinates may span $[-10^9, 10^9]$ while $n, m \leq 10^5$, direct array allocation is infeasible. However, only coordinates appearing in operations or query boundaries influence results. This motivates coordinate compression to map the sparse coordinate set to a dense contiguous range $[1, k]$ where $k \leq n + 2m$.

Algorithm Overview

1. Collection: Gather all positions from updates and all interval endpoints from queries into a single list.
2. Discretization: Sort the list and remove duplicates, establishing a mapping from original coordinates to ranks $1$ through $k$.
3. Accumulation: Apply all point increments using the compressed indices.
4. Prefix Summation: Compute cumulative sums over the compressed domain to answer range queries in constant time.
5. Query Processing: Map each query's endpoints to their compressed ranks and compute the difference of prefix sums.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAX_COORDS = 300010;

struct PointUpdate {
    int coord;
    int delta;
};

struct RangeQuery {
    int left;
    int right;
};

vector<int> compressed;
vector<PointUpdate> updates;
vector<RangeQuery> queries;
int values[MAX_COORDS];
int prefix[MAX_COORDS];

int getIndex(int x) {
    return lower_bound(compressed.begin(), compressed.end(), x) - compressed.begin() + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) {
        int x, c;
        cin >> x >> c;
        updates.push_back({x, c});
        compressed.push_back(x);
    }
    
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        queries.push_back({l, r});
        compressed.push_back(l);
        compressed.push_back(r);
    }
    
    sort(compressed.begin(), compressed.end());
    compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());
    
    for (const auto &op : updates) {
        int idx = getIndex(op.coord);
        values[idx] += op.delta;
    }
    
    for (int i = 1; i <= (int)compressed.size(); ++i) {
        prefix[i] = prefix[i - 1] + values[i];
    }
    
    for (const auto &q : queries) {
        int l = getIndex(q.left);
        int r = getIndex(q.right);
        cout << prefix[r] - prefix[l - 1] << '\n';
    }
    
    return 0;
}

The algorithm operates in $O((n+m) \log (n+m))$ time complexity due to sorting, with $O(n+m)$ space complexity. Each query is resolved in $O(1)$ time after preprocessing.