ผลรวมคำนำหน้าสูงสุดสำหรับช่วงที่กำหนดใน C++

ข้อความปัญหา

ได้รับอาร์เรย์ n จำนวนเต็ม และ q คำถาม (queries) แต่ละคำถามมีช่วงจาก l ถึง r ต้องการหาผลรวมคำนำหน้าสูงสุด (Maximum Prefix Sum) สำหรับช่วง l - r

ตัวอย่าง

ถ้าอาร์เรย์อินพุตคือ arr[] = {-1, 2, 3, -5} และ queries = 2 ช่วงคือ:
l = 0, r = 3
l = 1, r = 3
ผลลัพธ์จะเป็น 4 และ 5

• ช่วง (0, 3) ในคำถามแรกมี [-1, 2, 3, -5] เนื่องจากเป็น prefix ต้องเริ่มจาก -1 ดังนั้น max prefix sum = -1 + 2 + 3 = 4
• ช่วง (1, 3) ในคำถามที่สองมี [2, 3, -5] เนื่องจากเป็น prefix ต้องเริ่มจาก 2 ดังนั้น max prefix sum = 2 + 3 = 5

อัลกอริทึม

• สร้าง Segment Tree โดยแต่ละโหนดเก็บ 2 ค่า: sum (ผลรวม) และ prefix_sum (ผลรวมคำนำหน้า) และทำ Range Query เพื่อหา max prefix sums
• สำหรับการหาผลรวมคำนำหน้าสูงสุด ต้องการ 2 ค่า: ผลรวม และ prefix sum
• การรวม (Merge) จะคืนค่า 2 อย่าง: ผลรวมของช่วง และ prefix sum ที่เก็บ max(prefix.left, prefix.sum + prefix.right) ใน Segment Tree
• Max prefix sum สำหรับการรวม 2 ช่วง จะเป็น prefix sum จากด้านซ้าย หรือ ผลรวมด้านซ้าย + prefix sum ด้านขวา ขึ้นอยู่กับค่าที่มากกว่า

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

#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;
}

ผลลัพธ์

Result = -1

คำอธิบาย

Segment Tree นี้รองรับ Range Query สำหรับ Maximum Prefix Sum ได้ใน O(log n) ต่อคำถาม เหมาะสำหรับโจทย์ที่มีหลายคำถาม (Multiple Queries)