ภาพรวมปัญหา
กำหนดอาร์เรย์ที่ arr[i] = i × (-1)ⁱ (1-indexed) ต้องการหาผลรวมในช่วงดัชนี L ถึง R
ลำดับ: -1, 2, -3, 4, -5, 6, -7, 8, ...
- Index คี่: ค่าลบ (-i)
- Index คู่: ค่าบวก (+i)
ตัวอย่าง
L=2, R=6 arr[2]=2, arr[3]=-3, arr[4]=4, arr[5]=-5, arr[6]=6 Sum = 2 + (-3) + 4 + (-5) + 6 = 4
วิธีที่ 1: Brute Force O(R-L+1)
long long sumBruteForce(int L, int R) {
long long sum = 0;
for (int i = L; i <= R; i++) {
if (i % 2 == 0) sum += i; // Even: +i
else sum -= i; // Odd: -i
}
return sum;
}
วิธีที่ 2: สูตรคณิตศาสตร์ O(1)
แยกผลรวมเป็น: (ผลรวมเลขคู่) - (ผลรวมเลขคี่)
ผลรวมเลขคู่จาก 1 ถึง n:
Even Sum = 2 + 4 + ... + 2k = 2(1+2+...+k) = k(k+1) โดย k = floor(n/2)
ผลรวมเลขคี่จาก 1 ถึง n:
Odd Sum = 1 + 3 + ... + (2k-1) = k² โดย k = ceil(n/2) = (n+1)/2
ผลรวมในช่วง [L, R]:
Sum(L,R) = [EvenSum(R) - EvenSum(L-1)] - [OddSum(R) - OddSum(L-1)]
ตัวอย่างโค้ด C++ สมบูรณ์
#include <iostream>
using namespace std;
long long evenSum(long long n) {
// ผลรวมเลขคู่ 2+4+...+2k โดย k = n/2
long long k = n / 2;
return k * (k + 1);
}
long long oddSum(long long n) {
// ผลรวมเลขคี่ 1+3+...+(2k-1) โดย k = (n+1)/2
long long k = (n + 1) / 2;
return k * k;
}
long long rangeSumFormula(int L, int R) {
long long evenR = evenSum(R);
long long evenL = evenSum(L - 1);
long long oddR = oddSum(R);
long long oddL = oddSum(L - 1);
return (evenR - evenL) - (oddR - oddL);
}
long long rangeSumBruteForce(int L, int R) {
long long sum = 0;
for (int i = L; i <= R; i++) {
if (i % 2 == 0) sum += i;
else sum -= i;
}
return sum;
}
void testCase(int L, int R) {
cout << "L=" << L << ", R=" << R << endl;
cout << " Brute Force: " << rangeSumBruteForce(L, R) << endl;
cout << " Formula: " << rangeSumFormula(L, R) << endl;
// แสดงรายการ
cout << " Terms: ";
for (int i = L; i <= R; i++) {
int val = (i % 2 == 0) ? i : -i;
cout << val << " ";
}
cout << endl << endl;
}
int main() {
cout << "=== Sum of arr[i] = i*(-1)^i from L to R ===\n\n";
testCase(2, 6); // 2-3+4-5+6 = 4
testCase(3, 15); // -3+4-5+6-7+8-9+10-11+12-13+14-15 = -9
testCase(1, 10); // -1+2-3+4-5+6-7+8-9+10 = 5
testCase(1, 100); // Large test
testCase(1000000, 2000000); // Very large test (Formula only)
return 0;
}
ผลลัพธ์ตัวอย่าง
=== Sum of arr[i] = i*(-1)^i from L to R === L=2, R=6 Brute Force: 4 Formula: 4 Terms: 2 -3 4 -5 6 L=3, R=15 Brute Force: -9 Formula: -9 Terms: -3 4 -5 6 -7 8 -9 10 -11 12 -13 14 -15 L=1, 10 Brute Force: 5 Formula: 5 Terms: -1 2 -3 4 -5 6 -7 8 -9 10 L=1, 100 Brute Force: 50 Formula: 50 Terms: (many)... L=1000000, 2000000 Brute Force: (slow) Formula: 500000500000
การตรวจสอบสูตร (Verification)
| n | Even Sum | Odd Sum | Total (1 to n) |
|---|---|---|---|
| 1 | 0 | 1 | -1 |
| 2 | 2 | 1 | 1 |
| 3 | 2 | 4 | -2 |
| 4 | 6 | 4 | 2 |
| 5 | 6 | 9 | -3 |
| 6 | 12 | 9 | 3 |
| 10 | 30 | 25 | 5 |
| 100 | 2550 | 2500 | 50 |
รูปแบบที่สังเกตได้ (Pattern)
Sum(1 to n) = n/2 if n is even -(n+1)/2 if n is odd Sum(L to R) = Sum(1 to R) - Sum(1 to L-1)
โค้ดเวอร์ชันลดรูป (Simplified Formula)
long long prefixSum(long long n) {
if (n % 2 == 0) return n / 2;
return -(n + 1) / 2;
}
long long rangeSumSimple(int L, int R) {
return prefixSum(R) - prefixSum(L - 1);
}
ความซับซ้อนเปรียบเทียบ
| Method | Time | Space | Max N |
|---|---|---|---|
| Brute Force | O(R-L) | O(1) | ~10⁷ |
| Even/Odd Formula | O(1) | O(1) | 10¹⁸ |
| Simplified Prefix | O(1) | O(1) | 10¹⁸ |
ประยุกต์ใช้
- การคำนวณซีรีส์สลับเครื่องหมาย (Alternating Series)
- Digital Signal Processing
- Mathematical Programming Contests
- การพิสูจน์ทางคณิตศาสตร์ (Mathematical Induction)
