{"id":33596,"date":"2024-11-01T09:18:18","date_gmt":"2024-11-01T09:18:18","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33596"},"modified":"2024-11-01T11:47:29","modified_gmt":"2024-11-01T11:47:29","slug":"python-coding-test-course-finding-range-sum-3","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33596\/","title":{"rendered":"Python Coding Test Course, Finding Range Sum 3"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n Given an integer array A and several pairs of integers L and R, write a program to find the sum of the interval from index L to index R for each pair.\n <\/p>\n

\n For example, if A = [1, 2, 3, 4, 5] and the interval pairs are (1, 3), (0, 2), (2, 4),
\n the results should be 9, 6, and 12 respectively.\n <\/p>\n

Input Format<\/h2>\n
\n    - The first line contains an integer N (1 \u2264 N \u2264 100,000): size of array A\n    - The second line contains N integers A[i] (1 \u2264 A[i] \u2264 10,000).\n    - The third line contains an integer M (1 \u2264 M \u2264 100,000): number of interval pairs.\n    - The following M lines contain the interval pairs L, R (0 \u2264 L <= R < N).\n    <\/pre>\n
Output Format<\/h2>\n
\n    - Output the sum of each interval over M lines.\n    <\/pre>\n
Problem Solving Strategy<\/h2>\n
\n        While it is possible to solve this problem using simple loops,
\n        the worst-case scenario has N and M up to 100,000, making O(N * M) time complexity impossible.
\n        Therefore, a method with O(N + M) time complexity is needed.\n    <\/p>\n
\n        To achieve this, it is useful to create a prefix sum array<\/strong> as a preprocessing<\/strong> step.
\n        Using a prefix sum array allows for quick calculation of each interval’s sum.\n    <\/p>\n
Prefix Sum Array Description<\/h2>\n
\n        First, calculate the prefix sum of array A to create the prefix_sum array.
\n        prefix_sum[i] stores the sum from A[0] to A[i].
\n        Thus, the sum from index L to index R can be calculated as follows:
\n        
\nsum(L, R) = prefix_sum[R] – prefix_sum[L – 1]<\/strong>, L > 0
\n        
\nsum(0, R) = prefix_sum[R]<\/strong>, L = 0\n    <\/p>\n
Code Implementation<\/h2>\n
\n    \ndef compute_prefix_sum(A):\n    prefix_sum = [0] * len(A)\n    prefix_sum[0] = A[0]\n    for i in range(1, len(A)):\n        prefix_sum[i] = prefix_sum[i - 1] + A[i]\n    return prefix_sum\n\ndef range_sum(prefix_sum, L, R):\n    if L == 0:\n        return prefix_sum[R]\n    else:\n        return prefix_sum[R] - prefix_sum[L - 1]\n\ndef main():\n    N = int(input())\n    A = list(map(int, input().split()))\n    M = int(input())\n    \n    prefix_sum = compute_prefix_sum(A)\n\n    results = []\n    for _ in range(M):\n        L, R = map(int, input().split())\n        results.append(range_sum(prefix_sum, L, R))\n    \n    for result in results:\n        print(result)\n\nif __name__ == \"__main__\":\n    main()\n    <\/code>\n    <\/pre>\n
Code Explanation<\/h2>\n
\n        1. The compute_prefix_sum<\/strong> function calculates the prefix sum of the input array A and
\n        returns the prefix_sum array. It initializes the first value and calculates each index’s value by adding the previous value to the current value.\n    <\/p>\n
\n        2. The range_sum<\/strong> function quickly calculates the sum of the interval using the prefix sum array
\n        for the given L and R. If L is 0, it returns prefix_sum[R]; otherwise, it calculates the result by subtracting
\n        prefix_sum[L-1] from prefix_sum[R].\n    <\/p>\n
\n        3. The main<\/strong> function handles input and calls the range_sum function for each interval pair to display the results.\n    <\/p>\n
Time Complexity Analysis<\/h2>\n
\n        – It takes O(N) time to calculate the prefix sum array.\n    <\/p>\n
\n        – Each of the M queries takes O(1) time.
\n        Thus, the overall time complexity is O(N + M).\n    <\/p>\n
Conclusion<\/h2>\n
\n        In this lecture, we covered an efficient approach to finding interval sums.
\n        Utilizing prefix sums allows for reduced time complexity, enabling quick processing even for large inputs.
\n        This technique is useful in various algorithm problems, so it’s important to keep it in mind.\n    <\/p>\n
Additional Practice Problems<\/h2>\n