Truy vấn cặp tích lớn nhất trong đoạn với cập nhật C++

Cho mảng arr[] và Q truy vấn 2 loại:

1. Loại 1: 1 L R – Tìm tích lớn nhất của 2 phần tử khác nhau trong đoạn [L, R].
2. Loại 2: 2 i val – Cập nhật arr[i] = val.

Ví dụ

arr = {4, 2, 6, 9, 1}
Q1: 1 1 4 → đoạn {2,6,9,1} → max = 6*9 = 54
Q2: 2 2 3 → arr = {4,2,3,9,1}
Q3: 1 0 2 → đoạn {4,2,3} → max = 4*3 = 12

Phương pháp đơn giản O(N²) mỗi truy vấn

Duyệt tất cả cặp trong đoạn. Chậm nếu Q, N lớn.

Phương pháp tối ưu: Cây đoạn (Segment Tree)

Mỗi nút lưu 2 giá trị lớn nhất trong đoạn: max1, max2.

• Gộp 2 nút con: lấy 2 giá trị lớn nhất trong 4 giá trị max1_left, max2_left, max1_right, max2_right.
• Truy vấn loại 1: lấy max1, max2 của đoạn → tích.
• Cập nhật loại 2: cập nhật lá và kéo lên cha.

Độ phức tạp: O(log N) mỗi truy vấn/cập nhật.

Chương trình C++

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

struct Node {
    int max1, max2; // max1 >= max2
    Node(int m1 = -1, int m2 = -1) : max1(m1), max2(m2) {}
};

Node merge(const Node& a, const Node& b) {
    vector v = {a.max1, a.max2, b.max1, b.max2};
    sort(v.rbegin(), v.rend());
    return Node(v[0], v[1]);
}

class SegTree {
    vector tree;
    int n;
public:
    SegTree(const vector& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(1, 0, n-1, arr);
    }
    void build(int node, int l, int r, const vector& arr) {
        if (l == r) { tree[node] = Node(arr[l], -1); return; }
        int mid = (l + r) / 2;
        build(node*2, l, mid, arr);
        build(node*2+1, mid+1, r, arr);
        tree[node] = merge(tree[node*2], tree[node*2+1]);
    }
    void update(int idx, int val) { update(1, 0, n-1, idx, val); }
    void update(int node, int l, int r, int idx, int val) {
        if (l == r) { tree[node] = Node(val, -1); return; }
        int mid = (l + r) / 2;
        if (idx <= mid) update(node*2, l, mid, idx, val);
        else update(node*2+1, mid+1, r, idx, val);
        tree[node] = merge(tree[node*2], tree[node*2+1]);
    }
    Node query(int L, int R) { return query(1, 0, n-1, L, R); }
    Node query(int node, int l, int r, int L, int R) {
        if (R < l || r < L) return Node();
        if (L <= l && r <= R) return tree[node];
        int mid = (l + r) / 2;
        return merge(query(node*2, l, mid, L, R),
                     query(node*2+1, mid+1, r, L, R));
    }
};

int main() {
    vector arr = {4, 2, 6, 9, 1, 5};
    SegTree st(arr);
    
    cout << "Max product [1,4]: " << 1LL * st.query(1,4).max1 * st.query(1,4).max2 << endl; // 54
    st.update(2, 3);
    cout << "Max product [0,2]: " << 1LL * st.query(0,2).max1 * st.query(0,2).max2 << endl; // 12
    return 0;
}

Kết quả

Max product [1,4]: 54
Max product [0,2]: 12