Tiền tố tổng lớn nhất cho khoảng cho trước trong C++

Đề bài

Cho mảng n số nguyên và q truy vấn, mỗi truy vấn là khoảng [l, r]. Tìm max prefix-sum trong khoảng đó (tổng từ l đến một vị trí nào đó trong [l, r]).

Ví dụ

arr = {-1, 2, 3, -5}. Query 1: [0,3] → max prefix sum = -1+2+3 = 4. Query 2: [1,3] → max prefix sum = 2+3 = 5.

Thuật toán Segment Tree

Mỗi node lưu: sum (tổng đoạn) và prefix (max prefix sum của đoạn).

Merge: sum = left.sum + right.sum, prefix = max(left.prefix, left.sum + right.prefix).

Ví dụ minh họa

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

typedef struct node {
    int sum;
    int prefix;
} node;

node tree[4 * 10000];

void build(int *arr, int idx, int start, int end) {
    if (start == end) {
        tree[idx].sum = arr[start];
        tree[idx].prefix = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(arr, 2*idx+1, start, mid);
        build(arr, 2*idx+2, mid+1, end);
        tree[idx].sum = tree[2*idx+1].sum + tree[2*idx+2].sum;
        tree[idx].prefix = max(tree[2*idx+1].prefix, tree[2*idx+1].sum + tree[2*idx+2].prefix);
    }
}

node query(int idx, int start, int end, int l, int r) {
    node result;
    result.sum = result.prefix = -1;
    if (start > r || end < l) return result;
    if (start >= l && end <= r) return tree[idx];
    
    int mid = (start + end) / 2;
    if (l > mid) return query(2*idx+2, mid+1, end, l, r);
    if (r <= mid) return query(2*idx+1, start, mid, l, r);
    
    node left = query(2*idx+1, start, mid, l, r);
    node right = query(2*idx+2, mid+1, end, l, r);
    result.sum = left.sum + right.sum;
    result.prefix = max(left.prefix, left.sum + right.prefix);
    return result;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    build(arr, 0, 0, n-1);
    cout << "Result = " << query(0, 0, n-1, 3, 5).prefix << endl;
    return 0;
}

Kết quả

Result = -1

Giải thích: Query [3,5] tương ứng mảng con {-1, -2, 1}. Prefix sums: -1, -3, -2. Max = -1.

Độ phức tạp: Build O(n), Query O(log n). Phù hợp cho nhiều truy vấn.