C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34142\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm. Problem Description Given an … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Finding Interval Sums 2"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34142\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:24:42+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:26+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Finding Interval Sums 2\",\"datePublished\":\"2024-11-01T09:24:42+00:00\",\"dateModified\":\"2024-11-01T10:58:26+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\"},\"wordCount\":410,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34142\/\",\"name\":\"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:24:42+00:00\",\"dateModified\":\"2024-11-01T10:58:26+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34142\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Finding Interval Sums 2\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n","yoast_head_json":{"title":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34142\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm. Problem Description Given an … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Finding Interval Sums 2\"","og_url":"https:\/\/atmokpo.com\/w\/34142\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:24:42+00:00","article_modified_time":"2024-11-01T10:58:26+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34142\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34142\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Finding Interval Sums 2","datePublished":"2024-11-01T09:24:42+00:00","dateModified":"2024-11-01T10:58:26+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34142\/"},"wordCount":410,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34142\/","url":"https:\/\/atmokpo.com\/w\/34142\/","name":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:24:42+00:00","dateModified":"2024-11-01T10:58:26+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34142\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Finding Interval Sums 2"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34142"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142\/revisions"}],"predecessor-version":[{"id":34143,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142\/revisions\/34143"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":34142,"date":"2024-11-01T09:24:42","date_gmt":"2024-11-01T09:24:42","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34142"},"modified":"2024-11-01T10:58:26","modified_gmt":"2024-11-01T10:58:26","slug":"c-coding-test-course-finding-interval-sums-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34142\/","title":{"rendered":"C++ Coding Test Course, Finding Interval Sums 2"},"content":{"rendered":"

<\/p>\n

In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm.<\/p>\n

Problem Description<\/h2>\n
Given an array as follows, there will be several pairs of starting and ending indices provided. Write a program to calculate the range sum for each pair.<\/p>\n

Input<\/h3>\n

The first line contains the size of the array N (1 \u2264 N \u2264 100,000) and the number of queries M (1 \u2264 M \u2264 100,000).<\/li>\n
The second line contains N integers that are the elements of the array. Each element’s value is between -10,000 and 10,000 inclusive.<\/li>\n

Subsequently, M lines are given, each containing two integers S and E, which signify calculating the sum of the range [S, E]. (S, E use 1-based indexing.)<\/li>\n<\/ul>\n

Output<\/h3>\n
Print the range sum for each query on a new line.<\/p>\n

Problem Analysis<\/h2>\n
The problem of calculating the range sum is very inefficient, as directly calculating the sum results in a time complexity of O(N), making it O(N*M) when M is large. Therefore, in such cases, we can improve the calculation to O(1) using the prefix sum technique.<\/p>\n

Algorithm<\/h2>\n

Create a prefix sum array.<\/li>\n

For each query, use the start and end indices to calculate the range sum in O(1) time.<\/li>\n<\/ol>\n

Implementation<\/h3>\n

Now let\u2019s implement this algorithm in C++.<\/p>\n

\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n    int N, M;\n    cin >> N >> M;\n    \n    vector<int> arr(N + 1, 0);\n    vector<int> prefixSum(N + 1, 0);\n\n    \/\/ Input the array\n    for (int i = 1; i <= N; i++) {\n        cin >> arr[i];\n        prefixSum[i] = prefixSum[i - 1] + arr[i]; \/\/ Calculate the prefix sum\n    }\n\n    \/\/ Processing queries\n    for (int i = 0; i < M; i++) {\n        int S, E;\n        cin >> S >> E;\n        \/\/ Calculate the range sum\n        cout << prefixSum[E] - prefixSum[S - 1] << endl;\n    }\n\n    return 0;\n}\n    <\/code><\/pre>\nCode Explanation<\/h2>\nEach part of the code performs the following tasks:<\/p>\n
\nInput:<\/strong> Read N and M, then read N numbers and save them in the array arr.<\/li>\n
Create Prefix Sum Array:<\/strong> Generate a prefixSum array to calculate and store the sum up to the i-th element.<\/li>\n
Process Queries:<\/strong> For each query, read S and E, and compute the range sum in O(1) time using the prefixSum.<\/li>\n<\/ul>\nComplexity Analysis<\/h2>\nThe time complexity of this algorithm is as follows:<\/p>\n
\nCreating the prefix sum array: O(N)<\/li>\n
Processing each query: O(M)<\/li>\n
Total time complexity: O(N + M)<\/li>\n<\/ul>\nConclusion<\/h2>\nIn this lecture, we learned an efficient way to calculate the range sum. By using the prefix sum technique, we were able to avoid explicit looping and significantly reduce the time complexity. This technique can be applied to many problems, so it is important to master it.<\/p>\n
In the next lecture, we will cover more complex range sum problems using different data structures. Thank you!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm. Problem Description Given an … \ub354 \ubcf4\uae30 “C++ Coding Test Course, Finding Interval Sums 2”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34142","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34142\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm. Problem Description Given an … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Finding Interval Sums 2"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34142\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:24:42+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:26+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Finding Interval Sums 2\",\"datePublished\":\"2024-11-01T09:24:42+00:00\",\"dateModified\":\"2024-11-01T10:58:26+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\"},\"wordCount\":410,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34142\/\",\"name\":\"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:24:42+00:00\",\"dateModified\":\"2024-11-01T10:58:26+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34142\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Finding Interval Sums 2\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34142\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm. Problem Description Given an … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Finding Interval Sums 2\"","og_url":"https:\/\/atmokpo.com\/w\/34142\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:24:42+00:00","article_modified_time":"2024-11-01T10:58:26+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34142\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34142\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Finding Interval Sums 2","datePublished":"2024-11-01T09:24:42+00:00","dateModified":"2024-11-01T10:58:26+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34142\/"},"wordCount":410,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34142\/","url":"https:\/\/atmokpo.com\/w\/34142\/","name":"C++ Coding Test Course, Finding Interval Sums 2 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:24:42+00:00","dateModified":"2024-11-01T10:58:26+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34142\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34142\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Finding Interval Sums 2"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34142"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142\/revisions"}],"predecessor-version":[{"id":34143,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34142\/revisions\/34143"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

Problem Description<\/h2>\nGiven an array as follows, there will be several pairs of starting and ending indices provided. Write a program to calculate the range sum for each pair.<\/p>\n

Output<\/h3>\nPrint the range sum for each query on a new line.<\/p>\n

Problem Analysis<\/h2>\nThe problem of calculating the range sum is very inefficient, as directly calculating the sum results in a time complexity of O(N), making it O(N*M) when M is large. Therefore, in such cases, we can improve the calculation to O(1) using the prefix sum technique.<\/p>\n

Problem Description<\/h2>\n
Given an array as follows, there will be several pairs of starting and ending indices provided. Write a program to calculate the range sum for each pair.<\/p>\n

Output<\/h3>\n
Print the range sum for each query on a new line.<\/p>\n

Problem Analysis<\/h2>\n
The problem of calculating the range sum is very inefficient, as directly calculating the sum results in a time complexity of O(N), making it O(N*M) when M is large. Therefore, in such cases, we can improve the calculation to O(1) using the prefix sum technique.<\/p>\n