“This is my fourth day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

1. Title Description

Given an array of length N a[1], a[2],…. , a [n].

Then there are q queries, and each query takes two parameters, L, r.

For each query, print a[L]+a[L +1]+…. +a[r]

In plain English, the problem is to compute the sum of an array of intervals; We can directly calculate the interval sum by dividing the target interval and then summing up all the elements in the interval.

However, in this way, each time a target range is given, a calculation with time complexity O(r-L) is needed. If there are many target ranges given, the time consumption will be huge.

package main

import "fmt"

func main(a) {
    var n, q int
    fmt.Scan(&n, &q)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
    }
    // increments are performed each time, and time out when a large number of ranges are required
    for i := 0; i < q; i++ {
        var l, r int
        fmt.Scan(&l, &r)
        var ans int
        for j := l; j <= r; j++ {
            ans += a[j - 1]
        }
        fmt.Println(ans)
    }
}
Copy the code

Second, the problem solving

In this case, we can trade space for time.

First, we can preprocess the input, calculate the prefix and, get the corresponding prefix and array;

Then, the interval sum of L ~r is obtained by taking the difference between the values of r corresponding to the prefix and array subscripts and the values of l-1.

The following example verifies the above process, such as the following array:

Presum [I +1] = presum[I] + a[I] = presum[I] + a[I]; each prefix sum equals the previous prefix sum plus a new element.

(A [I] is actually a[i-1] of the array in the program.)

So let’s say we set l=3,r=4; The sum of the intervals we need to calculate is a[3] + a[4] = 3 + 4 = 7;

Two prefix and presum [4] = a [1] + [2] a + a + [3] a [4] = 10 presum [2] = a + [1] a [2] = 3 take poor:

Presum [4] -presum [2] = a[3] + a[4] is exactly the sum of intervals we need.

By using prefix and, O(n) extra storage space is used for prefix and array storage, but the time complexity of each query interval sum is directly reduced to O(1). Similar methods are often used in other questions.

Three, code implementation

package main

import "fmt"

func main(a) {
    var n, q int
    fmt.Scan(&n, &q)
    presum := make([]int, n + 1)
    for i := 0; i < n; i++ {
        var m int
        fmt.Scan(&m)
        presum[i+1] = presum[i] + m
    }
    for i := 0; i < q; i++ {
        var l, r int
        fmt.Scan(&l, &r)
        fmt.Println(presum[r] - presum[l- 1])}}Copy the code