Dãy con tăng tổng lớn nhất dùng Binary Indexed Tree (Fenwick) trong C++

Cho mảng arr[] N phần tử, tìm tổng lớn nhất của dãy con tăng (Strictly Increasing Subsequence) sử dụng Binary Indexed Tree (Fenwick Tree).

Ví dụ: arr=[4,1,9,2,3,7] → dãy con tăng max sum: 1,2,3,7 = 13.

Phương pháp BIT

• Nén tọa độ (coordinate compression): map giá trị mảng thành chỉ số 1..M theo thứ tự tăng.
• BIT lưu max sum kết thúc tại giá trị tương ứng.
• Duyệt mảng: với arr[i], query BIT prefix max tại index-1 → maxSum trước đó. Update BIT tại index với maxSum+arr[i].
• Kết quả = query BIT toàn bộ.

Ví dụ (C++)

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

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

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

int maxSumIS(int arr[], int n){
    map<int,int> arrMap;
    for(int i=0;i<n;i++) arrMap[arr[i]]=0;
    int idx=0;
    for(auto& it:arrMap) it.second=++idx;
    int* BITree=new int[idx+1]();
    for(int i=0;i<n;i++){
        int ms=calcMaxSum(BITree, arrMap[arr[i]]-1);
        updateBIT(BITree, idx, arrMap[arr[i]], ms+arr[i]);
    }
    return calcMaxSum(BITree, idx);
}

int main(){
    int arr[]={4,6,1,9,2,3,5,8};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout<<"Max sum increasing subsequence using BIT is "<<maxSumIS(arr,n);
    return 0;
}

Đầu ra

The Maximum sum increasing subsequence using Binary Indexed Tree is 19