Tìm mảng ban đầu từ mảng kết quả sau truy vấn cộng dồn C++

Cho mảng res[] kích thước N là kết quả sau các truy vấn [s, e, val] (cộng val vào các phần tử từ s đến e). Nhiệm vụ: khôi phục mảng ban đầu.

Ví dụ minh họa

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

Mảng ban đầu {4,0,7} → query {1,2,1} → {4,1,8} → query {0,1,3} → {7,4,8}.

Phương pháp giải

Thực hiện ngược các truy vấn: duyệt các query, trừ val khỏi các phần tử từ s đến e.

Ví dụ chương trình

#include <iostream> 
using namespace std; 

void calcInitialArrayQueries(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}};
    int n = sizeof(arr)/sizeof(arr[0]);
    int q = sizeof(query)/sizeof(query[0]);
    cout << "Mảng ban đầu: ";
    calcInitialArrayQueries(arr, n, query, q);
    return 0;
}

Kết quả

Mảng ban đầu: 7 0 7 -1 6