หา Initial Array จาก Range Sum Queries ใน C++

ในปัญหานี้ เราได้รับ array ผลลัพธ์ res[] และ queries [s, e, val] งานคือหา initial array ก่อนทำ query

Query Operation

แต่ละ query [s, e, val] เพิ่ม val ให้ทุก element index s ถึง e

ตัวอย่าง

Input: res[] = {7, 4, 8}, Queries = {{1, 2, 1}, {0, 1, 3}} Output: {4, 0, 7}

Initial: {4, 0, 7} → Query {1,2,1} → {4, 1, 8} → Query {0,1,3} → {7, 4, 8}

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

ทำย้อนกลับ: ลบ val จาก index s ถึง e สำหรับทุก query

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

#include <iostream>
using namespace std;

void findInitialArray(int arr[], int n, int query[][3], int q) {
    for (int i = 0; i < q; i++) {
        for (int j = query[i][0]; j <= query[i][1]; j++)
            arr[j] -= query[i][2];
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
}

int main() {
    int arr[] = {5, 1, 8, 2, 9};
    int query[][3] = {{0, 2, -2}, {1, 4, 3}};
    findInitialArray(arr, 5, query, 2);
    return 0;
}

ผลลัพธ์

Initial array: 7 0 7 -1 6

Optimization: ใช้ Difference Array ทำได้ใน O(N + Q) แทน O(N×Q)