Prefix Sum

Author: Neighborhood's Cat

---

Prefix Sum คือโครงสร้างข้อมูลที่ช่วยให้เราคำนวณผลรวมของช่วง (Range Sum Query) ได้อย่างรวดเร็ว โดยใช้เวลา \(\mathcal{O}(1)\) ต่อการตอบคำถาม หลังจากที่เราเตรียมข้อมูลเสร็จในเวลา \(\mathcal{O}(n)\).

ตัวอย่างโจทย์

กำหนดให้มีจำนวนเต็ม \(n\) ตัว และมีการถาม \(q\) ครั้ง โดยแต่ละครั้งจะถามว่า ผลรวมของตัวเลขตั้งแต่ตำแหน่ง \(l\) ถึง \(r\) มีค่าเท่าไร

Input

8
1 4 7 6 3 9 5 2
3
1 3
2 6
1 8

Output

12
29
37

วิธีการแก้ปัญหา

1. ขั้นตอนแรกสร้างอาเรย์ prefix[] ที่เก็บผลรวมสะสม เพื่อใช้สำหรับตอบคำถาม โดยจะทำการสร้างอะเรย์ขึ้นมาจำนวน \(n+1\) ช่อง เพื่อเก็บผลรวมของข้อมูลนำเข้าจากตำแหน่งที่ \(1\) ไปถึงตำแหน่งที่ \(k\) มีขั้นตอนดังนี้
   • กำหนด prefix[0] = 0

   • สำหรับ \(1 \le k \le N\)

     \(\text{prefix}[k] = \sum_{i=1}^{k}\text{arr}[i] = \text{prefix}[k-1] + \text{arr}[k]\)

     โดยขั้นตอนนี้ สามารถทำได้โดยการนำค่าของผลรวมช่องก่อนหน้า \(\text{prefix}[k-1]\) มารวมกับ \(\text{arr}[k]\) ซึ่งขั้นตอนนี้จะใช้เวลา \(\mathcal{O}(n)\)

### ตัวอย่างข้อมูลนำเข้าดังนี้

จากค่า arr ดังกล่าว เราสามารถสร้าง Array สำหรับ Prefix Sum ได้ดังนี้

| index   | 0 | 1 | 2 | 3  | 4  | 5  | 6  | 7  | 8  |
|---------|---|---|---|----|----|----|----|----|----|
| arr     | 0 | 1 | 4 | 7  | 6  | 3  | 9  | 5  | 2  |
| prefix  | 0 | 1 | 5 | 12 | 18 | 21 | 30 | 35 | 37 |

เช่น การคำนวน $\text{prefix}[3] = \text{prefix}[2] + \text{arr}[2] = 5 + 7 = 12$

1. เมื่อเราคำนวณออกมาแล้ว เราสามารถอบคำถามผลรวมตั้งแต่ \(l\) ถึง \(r\) ได้โดย

   \(\sum_{i=l}^{r}\text{arr}[i] = \text{prefix}[r] - \text{prefix}[l-1]\)

   เราสามารถนำมาลบกันได้ เนื่องจากว่าเราต้องการผลรวมแค่ \(l\) ถึง \(r\) แต่ \(\text{prefix}[r]\) คือผลรวมตั้งแต่ \(\text{arr}[1]\) ถึง \(\text{arr}[r]\) เราจึงต้องลบค่า \(\text{arr}[1]\) ถึง \(\text{arr}[l-1]\) ซึ่งก็คือ \(\text{prefix}[l-1]\) นั่นเอง

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   cin >> n;
   vector<long long> a(n+1, 0), prefix(n+1, 0);
   for (int i = 1; i <= n; i++) {
       cin >> a[i];
       prefix[i] = prefix[i-1] + a[i];
   }

   int q;
   cin >> q;
   while (q--) {
       int l, r;
       cin >> l >> r;
       cout << prefix[r] - prefix[l-1] << "\n";
   }
}

โจทย์เพิ่มเติม

บทเรียนนี้ยังไม่สมบูรณ์

หากใครต้องการช่วยเหลือ สามารถส่ง Pull Request มาได้ทาง GitHub