quicksum

quicksum (prefix sum, cumulative sum) เป็นเทคนิคที่ใช้ในการบวกเลขอย่างรวดเร็วเป็นช่วงบน array เดิมหลายๆครั้ง โดยอาศัยการคำนวณล่วงหน้า
ใช้เวลาในการคำนวณล่วงหน้า O$(n)$ และสามารถ query ข้อมูลได้ภายในเวลา $O(1)$

quicksum 1 มิติ

ปัญหา

เมื่อกำหนด array $A[1 \ .. \ n]$ มาให้ พร้อมกับค่า $a$ และ $b$ โดยที่ $1 \le a \le b \le n$ ให้ตอบคำถามว่าค่าของ

(1)
\begin{align} \sum_{i=a}^b A_i \end{align}

มีค่าเป็นเท่าไหร่

เช่น กำหนด array $[1,6,3,8,2,-4,6,7,1]$ ต้องการหาผลบวกในช่วง $[2,7]$ ก็จะได้คำตอบ $6+3+8+2+-4+6 = 21$

โดยปกติแล้ว สามารถตอบปัญหานี้ได้โดยการไล่บวกตามปกติ ดังนี้

#include <stdio.h>
 
int arr[100001];
 
int main(){
    int i,n,a,b,ans;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)scanf("%d", &arr[i]);
    scanf("%d %d", &a, &b);
    ans = 0;
    for(i = a; i <= b; i++)ans += arr[i];
    printf("%d\n",ans);
    return 0;
}

แน่นอนว่าหากมีการ query ข้อมูลเพียงครั้งเดียว วิธีนี้ย่อมเป็นวิธีที่ดีที่สุด โดยใช้เวลา $O(n)$
อย่างไรก็ตาม หากมีการ query ข้อมูล $m$ ครั้ง วิธีนี้จะใช้เวลา $O(mn)$ ซึ่งช้า

การทำ quicksum 1 มิติ

q1c.jpg

ให้ $A[1 \ .. \ n]$ เป็น array ที่เราจะทำการ quicksum
สามารถสร้าง array $B$ ซึ่ง $B[i] = A[1] + \ ... \ + A[i]$
เนื่องจาก $B[i-1] = A[1] + \ ... \ + A[i-1]$ ดังนั้น $B[i] = B[i-1] + A[i] \ \ ; \ \ 1 \lt i \le n$

หรือถ้าจะให้อธิบายตามรูป $B[i]$ คือพื้นที่สีเหลือง + พื้นที่สีชมพู , $B[i-1]$ คือพื้นที่สีเหลือง และ $A[i]$ คือพื้นที่สีชมพู
ดังนั้น $B[i] = B[i-1] + A[i]$

จากความสัมพันธ์ข้างต้นนี้ สามารถสร้าง array $B$ ได้ภายในเวลา $O(n)$

การ query quicksum 1 มิติ

q1q.jpg

การ query ข้อมูลในแต่ละครั้งนั้น คือการหาผลบวกในช่วง $[a,b] \ \ ; \ \ 1 \le a \le b \le n$
เนื่องจาก $B[a-1] = A[1] + \ ... \ + A[a-1]$
และ $B[b] = A[1] + \ ... \ + A[a-1] + (A[a] + \ ... \ + A[b])$
ดังนั้น $A[a] + \ ... \ + A[b] = B[b] - B[a-1] \ \ ; \ \ 1 \lt a \le b \le n$

หรือถ้าจะให้อธิบายตามรูป $B[b]$ คือพื้นที่สีเขียว + พื้นที่สีฟ้า , $B[a-1]$ คือพื้นที่สีเขียว
และสิ่งที่ต้องการหาคือ $A[a] + \ ... \ + A[b]$ คือพื้นที่สีฟ้า
ดังนั้น $A[a] + \ ... \ + A[b] = B[b] - B[a-1]$

ในการทำ quicksum จริงๆ สามารถสร้าง array $B$ ทับ array $A$ ได้เลย เนื่องจากไม่มีความจำเป็นในการใช้ array $A$ อีกต่อไป
(การจะหา $A[s] \ \ ; \ \ 1 \le s \le n$ สามารถหาได้จาก $A[s] = B[s] - B[s-1] \ \ ; \ \ 1 \lt s \le n$)

ข้อควรระวัง

ในสมการความสัมพันธ์นั้น จะใช้ได้เมื่อ $i \gt 1$ เท่านั้น ทำให้ต้องดักกรณีพิเศษเมื่อมีการ query ข้อมูลตัวแรก ซึ่งยุ่งยากและเสียเวลา

มีวิธีการแก้อย่างง่ายคือ เลื่อน index ไปจัดเก็บในช่องที่สองเป็นต้นไปแทน และปล่อยช่องแรกทิ้งไว้ (กำหนดค่าช่องแรกเป็น 0)
ในภาษา C นั้น ช่องแรกของ array คือ $A[0]$ ดังนั้นเพียงกำหนด $A[0] = 0$ ก็สามารถใช้สมการความสัมพันธ์ได้โดยไม่ต้องกังวลเรื่องขอบเขตช่วง

code quicksum 1 มิติ

#include <stdio.h>
 
int arr[100001];
 
int main(){
    int i,n,q,l,r;
    scanf("%d", &n);
    arr[0] = 0;
    for(i = 1; i <= n; i++){
        scanf("%d", &arr[i]);
        arr[i] += arr[i-1];
    }
    scanf("%d", &q);
    for(i = 1; i <= q; i++){
        scanf("%d %d", &l, &r);
        printf("%d\n", arr[r] - arr[l-1]);
    }
    return 0;
}

quicksum 2 มิติ

ปัญหา

เป็นปัญหาเช่นเดียวกันกับ quicksum 1 มิติ แต่เปลี่ยนจากการหาผลบวกเป็นช่วงบน array 1 มิติ เป็นการหาผลบวกเป็นพื้นที่บน array 2 มิติแทน

กล่าวคือเมื่อกำหนด array $A[1 \ .. \ m][1 \ .. \ n]$ มาให้ พร้อมกับค่า $a , b , c , d$ โดยที่ $1 \le a \le c \le m$ และ $1 \le b \le d \le n$ ให้ตอบคำถามว่าค่าของ

(2)
\begin{align} \sum_{i=a}^b \left ( \sum_{j=b}^d A_{ij} \right ) \end{align}

มีค่าเป็นเท่าไหร่

การทำ quicksum 2 มิติ

q2c.jpg

ใช้แนวคิดเช่นเดียวกันกับ quicksum 1 มิติ
จากรูป ให้ $A$ เป็น array 2 มิติที่จะทำ quicksum โดยมีขนาด $m \times n$
จะสามารถสร้าง array $B$ ขึ้นมา โดย
$B[i][j]$ คือพื้นที่สีชมพู + พื้นที่สีเขียว + พื้นที่สีฟ้า + พื้นที่สีเหลือง
$B[i][j-1]$ คือพื้นที่สีชมพู + พื้นที่สีฟ้า
$B[i-1][j]$ คือพื้นที่สีชมพู + พื้นที่สีเขียว
$B[i-1][j-1]$ คือพื้นที่สีชมพู
$A[i][j]$ คือพื้นที่สีเหลือง
เห็นได้ว่า $B[i][j] = A[i][j] + B[i-1][j] + B[i][j-1] - B[i-1][j-1]$

จากความสัมพันธ์ข้างต้นนี้ สามารถสร้าง array $B$ ได้ภายในเวลา $O(mn)$

การ query quicksum 2 มิติ

q2q.jpg

การ query ข้อมูลในแต่ละครั้งนั้น คือการหาผลบวกในพื้นที่สีเหลือง (จาก $(a,b)$ ไปถึง $(c,d)$ โดยที่ $1 \le a \le c \le m$ และ $1 \le b \le d \le n$)
จากรูป $B[c][d]$ คือพื้นที่สีเหลือง + พื้นที่สีเขียว + พื้นที่สีฟ้า + พื้นที่สีชมพู
$B[a-1][d]$ คือพื้นที่สีเขียว + พื้นที่สีชมพู
$B[c][b-1]$ คือพื้นที่สีฟ้า + พื้นที่สีชมพู
$B[a-1][b-1]$ คือพื้นที่สีชมพู
และสิ่งที่ต้องการหาคือพื้นที่สีเหลือง
จะสังเกตได้ว่า พื้นที่สีเหลือง $= B[c][d] - B[a-1][d] - B[c][b-1] + B[a-1][b-1]$

ข้อควรระวัง

เช่นเดียวกันกับ quicksum 1 มิติ คือความสัมพันธ์ต่างๆจะใช้ได้เมื่อ $i \gt 1 , j \gt 1$
สามารถแก้ไขปัญหานี้ได้ด้วยวิธีเดียวกันกับแบบ 1 มิติ คือกำหนด $A[0][*] = A[*][0] = 0$

code quicksum 2 มิติ

#include <stdio.h>
 
int arr[1001][1001];
 
int main(){
    int r,c,i,j,q,a,b,c,d;
    scanf("%d %d", &r, &c);
    for(i = 0; i <= r; i++)arr[i][0] = 0;
    for(i = 0; i <= c; i++)arr[0][i] = 0;
    for(i = 1; i <= r; i++){
        for(j = 1; j <= c; j++){
            scanf("%d", &arr[i][j]);
            arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
        }
    }
    scanf("%d", &q);
    for(i = 1; i <= q; i++){
        scanf("%d %d %d %d", &a, &b, &c, &d);
        printf("%d\n", arr[c][d] - arr[a-1][d] - arr[c][b-1] + arr[a-1][b-1]);
    }
    return 0;
}

quicksum n มิติ

ใช้ หลักการเพิ่มเข้าและตัดออก ในการหาความสัมพันธ์ต่างๆ

ข้อจำกัด quicksum

quicksum นั้นจะต้องทำเมื่อรับ input เข้ามาครบหมดแล้วเท่านั้น ไม่สามารถทำไป query ไปได้
ซึ่งในกรณีที่ต้องการทำไป query ไปนั้น จะต้องใช้ Fenwick tree ซึ่งการดำเนินการใดๆใช้เวลา $O(\log n)$ ($m$ ครั้งเป็น $O(m \log n)$)

อ่านเพิ่มเติม

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License