1. Introduction<\/h2>\n
\n Hello. In this session, we will learn about how to efficiently calculate the interval sum in Kotlin. \n Given a sequence \n Print the result for each query one line at a time.\n <\/p>\n \n There are several ways to calculate the interval sum, but the basic approaches are as follows.\n <\/p>\n \n The most intuitive method is to directly calculate the sum in the defined range for each query. However, this method has a time complexity of O(N), and in the worst case, it becomes O(N * M) = O(10^10) when the maximum number of queries is 100,000, making it very inefficient.\n <\/p>\n \n By using the following methodology, we can efficiently calculate the interval sum. \n Let’s implement the interval sum calculation algorithm using the cumulative sum array in Kotlin.\n <\/p>\n \n The key point in the above implementation is that we can process each query in O(1) through \n Analyzing the time complexity of this algorithm, we have:\n <\/p>\n \n Therefore, under the given constraints, we can efficiently calculate the interval sum.\n <\/p>\n<\/section>\n
\n This is one of the problems frequently encountered in coding tests, where we need to find the sum over a specific interval of a given sequence.
\n Through this process, we will discuss various methods to solve the interval sum problem and their respective time complexities.\n <\/p>\n<\/section>\n2. Problem Description<\/h2>\n
A<\/code> and a query Q<\/code>, each query is given by two integers L<\/code> and R<\/code>.
\n We need to quickly find the sum from L<\/code> to R<\/code>.\n <\/p>\nInput<\/h3>\n
\n
N<\/code> and the number of queries M<\/code>.<\/li>\nN<\/code> integers forming the sequence A<\/code>.<\/li>\nM<\/code> lines, L<\/code> and R<\/code> are given.<\/li>\n<\/ul>\nOutput<\/h3>\n
Constraints<\/h3>\n
\n
1 \u2264 N \u2264 100,000<\/code><\/li>\n1 \u2264 M \u2264 100,000<\/code><\/li>\n-1,000,000,000 \u2264 A[i] \u2264 1,000,000,000<\/code><\/li>\n<\/ul>\n<\/section>\n3. Approach<\/h2>\n
3.1. Simple Iteration<\/h3>\n
3.2. Cumulative Sum Array<\/h3>\n
\n
\n A cumulative sum array is an array that pre-calculates the sum up to a specific position, which can be created in linear time O(N).
\n This allows each query to be processed in O(1). Thus, the overall time complexity is O(N + M).\n <\/p>\n<\/section>\n4. Implementation<\/h2>\n
\n
\nfun main() {\n val reader = System.`in`.bufferedReader()\n val (n, m) = reader.readLine().split(\" \").map { it.toInt() }\n\n val array = reader.readLine().split(\" \").map { it.toInt() }.toIntArray()\n val sumArray = IntArray(n + 1)\n\n \/\/ Create cumulative sum array\n for (i in 1..n) {\n sumArray[i] = sumArray[i - 1] + array[i - 1]\n }\n\n val result = StringBuilder()\n \/\/ Process queries\n repeat(m) {\n val (l, r) = reader.readLine().split(\" \").map { it.toInt() }\n val sum = sumArray[r] - sumArray[l - 1]\n result.append(sum).append(\"\\n\")\n }\n\n println(result)\n}\n<\/code>\n <\/pre>\nsumArray<\/code>.
\n The sum of the interval [L, R] can be easily calculated as sumArray[R] - sumArray[L-1]<\/code>.\n <\/p>\n<\/section>\n5. Time Complexity Analysis<\/h2>\n
\n
6. Example<\/h2>\n
6.1. Input Example<\/h3>\n
\n
\n5 3\n1 2 3 4 5\n1 3\n2 5\n1 5\n<\/code>\n <\/pre>\n6.2. Output Example<\/h3>\n
\n
\n6\n14\n15\n<\/code>\n <\/pre>\n