# Interval sum

Source = > AcWing802 question

### subject

Suppose there is an infinite number axis, and the number on each coordinate on the number axis is 0.

Now, let's start with n operations, each of which adds c to the number at a certain position x.

Next, make m queries. Each query contains two integers L and r. you need to find the sum of all numbers between the interval [l,r].

### Input format

The first line contains two integers n and m.

Next n lines, each containing two integers x and c.

Next m lines, each containing two integers l and r.

### Output format

There are m lines in total, and each line outputs the sum of numbers in the interval obtained in a query.

### Data range

−109≤x≤109,

1≤n,m≤105,

−109≤l≤r≤109,

−10000≤c≤10000

### Input example:

3 3

1 2

3 6

7 5

1 3

4 6

7 8

### Output example:

8

0

5

### Implementation code:

//2021 10 12 section and #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; vector<int> alls; // It is used to store the values of all subscripts and the endpoints of the interval (- 2e9 ~ 2e9) vector<PII> add; // Store the subscript and corresponding value of the interval sum to be calculated vector<PII> query; // Store the interval to be calculated and int a[N], s[N]; // a[N] used to store the discretized array s[N] used to store the array prefix and // The find() function maps the value of the original subscript (passed in) to a new subscript (returned) to realize discretization int find(int x) { // x is the subscript of array a[N], and is the value of array all 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; } /** * You can also implement the unique() function yourself * Ordered array de duplication function unique() vector<int>::iterator unique(vector<int> &a) { int j = 0; for (int i = 0; i < a.size(); i ++ ) if (!i || a[i] != a[i - 1]) a[j ++ ] = a[i]; // a[0] ~ a[j - 1] Non repeating numbers in all a return a.begin() + j; } **/ int main(){ int n, m; cin >> n >> m; while(n--){ int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } while(m--){ int l, r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } // De duplication (remove duplicate points) sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()), alls.end()); // Process insert for (auto item : add) { int x = find(item.first); // Find the subscript and map it to the new subscript x according to the original subscript item.frist a[x] += item.second; // The value corresponding to the subscript is written into the array a[x] } // Calculate prefix and for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // Handling inquiries for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }

### Problem solving ideas

First, analyze the topic. The data range of the topic is [− 109109], but the amount of data is only [− 1000010000]. Therefore, it is obviously impossible to directly store the input data location with the array subscript. Therefore, we can use the discretization method.

The essence of discretization is mapping, mapping points with large intervals to adjacent array elements. Reduce the demand for space and reduce the amount of calculation.

Discretization, mapping the limited individuals in infinite space to the limited space, so as to improve the space-time efficiency of the algorithm.

Generally speaking, discretization is to reduce the data without changing the relative size of the data.

In this topic, we can open up a container (all) to store the location of input data. The mapping relationship is formed by finding the position of the data position in the container. For this, the find() function can be constructed to implement this mapping relationship. The incoming data location (large and scattered value) returns its location in the container (all) (small value and continuous point). In this way, the abscissa of discontinuous points on the number axis is mapped into the subscript of the new array.

In addition, the container (all) needs to store not only the original number axis subscript, but also the left and right endpoints of the sum in the interval we need to find. This is because the breakpoints at both ends of the sum in the interval we need to find do not necessarily have elements. Adding two endpoints requiring prefix sum in advance is conducive to our binary search. Then you need to sort and remove the duplicate.

### epilogue

Thanks for watching! Your advice are most welcome!