\n Hello! In this post, we will take a closer look at how to solve the problem of calculating the sum of intervals using Kotlin.
\n The interval sum problem is a common type encountered in programming contests and coding tests, and knowing how to solve it efficiently can help you quickly solve various problems.\n <\/p>\n
\n The task is to calculate the sum of a specific interval when given an array. The aim is to solve the problem of \n In this case, when we receive a query to find the sum in the interval (i, j) specified by the user, \n The first line contains the size of the array \n Print the sum for each query.\n <\/p>\n \n There are two ways to solve this problem. \n By using a prefix sum array, we can calculate the interval sum in O(1) time complexity for each query. \n A prefix sum array is an array that stores the cumulative sums of a given array. \n The sum from \n Here, \n Now, let\u2019s write the code to solve this problem using Kotlin.\n <\/p>\n
\n calculating the sum for each interval given the array and several queries. For example, let’s assume the array A<\/code> is as follows:\n <\/p>\n\n A = [10, 20, 30, 40, 50]\n <\/pre>\n
\n we need to return the corresponding sum.\n <\/p>\nInput Format<\/h2>\n
N<\/code> and the number of queries M<\/code>.
\n Then, N<\/code> integers are provided to form the array A<\/code>.
\n The next M<\/code> lines each contain two integers i<\/code> and j<\/code>,
\n indicating a query to calculate the sum from A[i]<\/code> to A[j]<\/code>.\n <\/p>\nOutput Format<\/h2>\n
Example Input<\/h3>\n
\n 5 3\n 10 20 30 40 50\n 1 3\n 2 4\n 1 5\n <\/pre>\n
Example Output<\/h3>\n
\n 60\n 90\n 150\n <\/pre>\n
Approach to Solve the Problem<\/h2>\n
\n The first method is to simply iterate and calculate the sum for each query,
\n and the second is to use the prefix sum array<\/strong>.
\n The second method is much more efficient, so I will focus on explaining that.\n <\/p>\nPrefix Sum Array<\/h3>\n
\n Since calculating the prefix sum array takes O(N) time,
\n the total time complexity is O(N + M).
\n This becomes more efficient as the number of queries increases.\n <\/p>\nDefinition of Prefix Sum Array<\/h4>\n
\n Specifically, we define an array S<\/code> that stores the sum up to the i-th index of array A<\/code>.
\n It is represented as S[i] = A[0] + A[1] + ... + A[i-1]<\/code>.\n <\/p>\nHow to Calculate Interval Sums<\/h4>\n
A[i]<\/code> to A[j]<\/code> can be calculated as follows:
\n sum = S[j+1] - S[i]<\/code>\n<\/p>\nS[j+1]<\/code> is the sum from A[0]<\/code> to A[j]<\/code>,
\n and S[i]<\/code> is the sum from A[0]<\/code> to A[i-1]<\/code>.
\n Therefore, by subtracting S[i]<\/code> from S[j+1]<\/code>, we obtain the sum from A[i]<\/code> to A[j]<\/code>.\n <\/p>\nCode Implementation<\/h2>\n
Kotlin Code<\/h3>\n
\n fun main() {\n val (n, m) = readLine()!!.split(\" \").map { it.toInt() }\n val a = readLine()!!.split(\" \").map { it.toInt() }\n \n val s = IntArray(n + 1)\n \n for (i in 1..n) {\n s[i] = s[i - 1] + a[i - 1]\n }\n \n repeat(m) {\n val (i, j) = readLine()!!.split(\" \").map { it.toInt() }\n println(s[j] - s[i - 1])\n }\n }\n <\/pre>\nCode Explanation<\/h2>\n