\n Hello! Welcome to the Python coding test course. In this course, we will
\n cover the “Interval Sum Problem 2”. Efficiently calculating the interval sum
\n is very important in solving algorithm problems.
\n Below, we will look at the problem description and solution process step by step.\n <\/p>\n
\n Given N integers A[1], A[2], …, A[N],
\n Q queries are provided. Each query consists of two integers L and R,
\n and the goal is to find the sum from A[L] to A[R].
\n The problem is as follows:\n <\/p>\n
\nInput Format:<\/strong>
\n The first line contains the integers N (1 \u2264 N \u2264 100,000) and Q (1 \u2264 Q \u2264 100,000).
\n The second line contains N integers separated by spaces. |A[i]| \u2264 1,000,000
\n The Q queries are given as follows: each query consists of two integers L and R (1 \u2264 L \u2264 R \u2264 N).\n <\/p><\/blockquote>\n\nOutput Format:<\/strong>
\n Print the sum from A[L] to A[R] for each query.\n <\/p>\nHow to Solve the Problem Efficiently<\/h2>\n
\n To solve such problems, it is efficient to use the prefix sum
\n instead of calculating the sum for each query.
\n The prefix sum allows you to calculate the sum of a specific interval in constant time O(1).\n <\/p>\nCalculating Prefix Sum<\/h3>\n
\n The method to calculate the prefix sum is as follows:\n <\/p>\n
\n
- Create a prefix sum array S, where S[i] represents the sum from A[1] to A[i].<\/li>\n
- Initialize S[0] = 0. (For convenience, 0 is added so that the calculation can be done by subtracting S[L-1] from S[i].)<\/li>\n
- Then calculate S[i] as follows: S[i] = S[i-1] + A[i]<\/li>\n<\/ul>\n
\n This allows us to find the interval sum with a single subtraction operation as S[R] – S[L-1].\n <\/p>\n
Solution Code<\/h3>\n
\n\ndef calculate_prefix_sum(arr):\n n = len(arr)\n prefix_sum = [0] * (n + 1)\n for i in range(1, n + 1):\n prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]\n return prefix_sum\n\ndef range_sum(prefix_sum, L, R):\n return prefix_sum[R] - prefix_sum[L - 1]\n\nN, Q = map(int, input().split())\nA = list(map(int, input().split()))\nprefix_sum = calculate_prefix_sum(A)\n\nfor _ in range(Q):\n L, R = map(int, input().split())\n print(range_sum(prefix_sum, L, R))\n <\/code>\n <\/pre>\n\n The above code performs the following steps:\n <\/p>\n
\n
- First, it calls a function to calculate the prefix sum array for the given array A of length N.<\/li>\n
- For each query, it receives L and R, and outputs the sum for that interval.<\/li>\n<\/ul>\n
Time Complexity Analysis<\/h2>\n
\n Analyzing the time complexity of this problem yields the following:\n <\/p>\n