Tối đa hóa tổng mảng trong K bước di chuyển [L, R] trong C++

Cho mảng Arr[] và các truy vấn Q[i] = {lpos, rpos, K}. Từ lpos di chuyển đến rpos trong tối đa K bước (mỗi bước +1 hoặc đứng yên). Cộng giá trị tại mỗi bước (kể cả vị trí đầu). Tối đa hóa tổng. Nếu không thể đến rpos trong K bước → "NO".

Ví dụ

Đầu vào: Arr[] = {1, 2, 4, -1}, Q = {{0,2,2}, {0,2,1}, {3,3,1}, {0,2,3}}

Đầu ra: Query 1: 7 (0→1→2: 1+2+4). Query 2: NO (cần 2 bước). Query 3: NO. Query 4: 11 (0→1→2→stay: 1+2+4+4).

Phương pháp: Segment Tree + Prefix Sum

• Xây Segment Tree tìm max trên đoạn [lpos, rpos].
• Prefix sum tính tổng đoạn [lpos, rpos].
• Nếu rpos - lpos > K → NO.
• Tổng = sum(lpos..rpos) + (K - (rpos-lpos)) * maxVal (ở lại vị trí max nhất).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

void createTree(int mn, int mx, int pos, int sgT[], int arr[], int len) {
    if (mn == mx) { sgT[pos] = arr[mx]; return; }
    int mid = (mn+mx)/2;
    createTree(mn, mid, 2*pos+1, sgT, arr, len);
    createTree(mid+1, mx, 2*pos+2, sgT, arr, len);
    sgT[pos] = max(sgT[2*pos+1], sgT[2*pos+2]);
}

int findMax(int st, int en, int ql, int qr, int pos, int sgT[], int arr[], int len) {
    if (ql <= st && qr >= en) return sgT[pos];
    if (en < ql || st > qr) return INT_MIN;
    int mid = (st+en)/2;
    return max(findMax(st, mid, ql, qr, 2*pos+1, sgT, arr, len),
               findMax(mid+1, en, ql, qr, 2*pos+2, sgT, arr, len));
}

int solQuery(int lpos, int rpos, int k, int len, int arr[], int sgT[], int pSum[]) {
    if (rpos - lpos > k) return -1;
    int maxVal = findMax(0, len-1, lpos, rpos, 0, sgT, arr, len);
    if (maxVal < 0) maxVal = 0;
    int sum = pSum[rpos] - (lpos > 0 ? pSum[lpos-1] : 0);
    return sum + (k - (rpos - lpos)) * maxVal;
}

void preSum(int pSum[], int arr[], int len) {
    pSum[0] = arr[0];
    for (int i=1; i

Đầu ra chương trình
Query 1: 7
Query 2: NO
Query 3: NO
Query 4: 11