โปรแกรม C พิมพ์อาร์เรย์หลังปรับเปลี่ยนช่วงหลายครั้ง (Range Increment Operations)

โจทย์

กำหนดอาร์เรย์ arr[m], ค่า n ที่จะบวก, และ r queries แต่ละ query มี start และ end index สำหรับแต่ละ query ให้บวก n เข้าไปในอาร์เรย์ตั้งแต่ start ถึง end แล้วพิมพ์อาร์เรย์หลังแต่ละ query

ตัวอย่าง

Input: arr = {1, 2, 3, 4, 5}, n = 2
Queries: {0, 3}, {1, 2}

Query 1: เพิ่ม 2 ที่ index 0-3 → {3, 4, 5, 6, 5}
Query 2: เพิ่ม 2 ที่ index 1-2 → {3, 6, 7, 6, 5}

อัลกอริทึม (Naive Approach)

1. สร้าง struct range {int start, end;}
2. ฟังก์ชัน add_tomatrix(arr, queries, n, size, m):
3. วนลูปทุก query i = 0..m-1
4. วนลูป j = queries[i].start ถึง queries[i].end: arr[j] += n
5. พิมพ์อาร์เรย์ทั้งหมดหลัง query นั้น

โค้ดภาษา C

#include <stdio.h>

struct range {
    int start, end;
};

int add_tomatrix(int arr[], struct range r[], int n, int size, int m) {
    int i, j, k;
    for (i = 0; i < m; i++) {
        for (j = r[i].start; j <= r[i].end; j++)
            arr[j] += n;
        printf("Query %d: ", i + 1);
        for (k = 0; k < size; k++)
            printf(" %d", arr[k]);
        printf("\n");
    }
    return 0;
}

int main() {
    int arr[] = {3, 4, 8, 1, 10};
    struct range r[] = {{0, 2}, {1, 3}, {3, 4}};
    int n = 2;
    int size = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(r) / sizeof(r[0]);
    add_tomatrix(arr, r, n, size, m);
    return 0;
}

ผลลัพธ์

Query 1: 5 6 10 1 10
Query 2: 5 8 12 3 10
Query 3: 5 8 12 5 12

หมายเหตุ: วิธีนี้ใช้เวลา O(m × n) สำหรับ m queries และ n ขนาดอาร์เรย์ สามารถปรับปรุงได้ด้วย Difference Array / Prefix Sum ให้เป็น O(m + n)