Tìm dãy con tăng dần có tổng lớn nhất sử dụng Cây chỉ số nhị phân (BIT) trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n số nguyên. Nhiệm vụ là viết chương trình tìm dãy con tăng dần có tổng lớn nhất sử dụng cây chỉ số nhị phân (Binary Indexed Tree) trong C++.

Mô tả bài toán

Chúng ta cần tìm một dãy con tăng dần có tổng lớn nhất sử dụng các phần tử của mảng.

Dãy con tăng dần (Increasing Subsequence)

Dãy con mà giá trị phần tử hiện tại lớn hơn giá trị phần tử tại vị trí trước đó.

Cây chỉ số nhị phân (Binary Indexed Tree - BIT)

Là một cấu trúc dữ liệu dạng cây. Cho phép thêm hoặc xóa phần tử khỏi cây một cách hiệu quả.

Ví dụ minh họa

Đầu vào

arr[] = {5, 1, 7, 3, 8, 2}

Đầu ra

20

Giải thích

Các dãy con: {5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16

Phương pháp giải

Trong bài toán này, ta cần tìm maxSum có thể bằng cách sử dụng cây chỉ số nhị phân. Ta sẽ tạo một cây chỉ số nhị phân sử dụng map từ các phần tử của mảng. Sau đó, duyệt qua các phần tử của mảng, với mỗi phần tử ta cần tìm tổng của tất cả các phần tử đến giá trị đó trong BIT. Sau đó trả về tổng lớn nhất của tất cả các giá trị.

Chương trình minh họa

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

int calcMaxSum(int BITree[], int index) {
    int sum = 0;
    while (index > 0) {
        sum = max(sum, BITree[index]);
        index -= index & (-index);
    }
    return sum;
}

void updateTreeVal(int BITree[], int newIndex, int index, int sumVal) {
    while (index <= newIndex) {
        BITree[index] = max(sumVal, BITree[index]);
        index += index & (-index);
    }
}

int calcMaxSumBIT(int arr[], int n) {
    int uniqCount = 0, maxSum;
    map<int, int> BinaryIndexTree;
    
    for (int i = 0; i < n; i++) {
        BinaryIndexTree[arr[i]] = 0;
    }
    
    for (map<int, int>::iterator it = BinaryIndexTree.begin();
         it != BinaryIndexTree.end(); it++) {
        uniqCount++;
        BinaryIndexTree[it->first] = uniqCount;
    }
    
    int* BITree = new int[uniqCount + 1];
    for (int i = 0; i <= uniqCount; i++) {
        BITree[i] = 0;
    }
    
    for (int i = 0; i < n; i++) {
        maxSum = calcMaxSum(BITree, BinaryIndexTree[arr[i]] - 1);
        updateTreeVal(BITree, uniqCount, BinaryIndexTree[arr[i]],
                      maxSum + arr[i]);
    }
    
    return calcMaxSum(BITree, uniqCount);
}

int main() {
    int arr[] = {5, 1, 7, 3, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Dãy con tăng dần có tổng lớn nhất sử dụng BIT là "
         << calcMaxSumBIT(arr, n);
    return 0;
}

Đầu ra

Dãy con tăng dần có tổng lớn nhất sử dụng BIT là 20