平衡子序列的最大和

给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：
对于范围 [1, k - 1] 内的所有 j ，nums[i] - nums[j] >= i - j 都成立。
nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数，表示 nums 平衡子序列里面的最大元素和 。

1. 离散化树状数组

树状数组求左侧闭区间最大值

class Solution {
public:
    vector<long long> tree;
    int idx = 1;
    long long maxBalancedSubsequenceSum(vector<int>& nums) {
        //要满足nums[i]-nums[j]>=i-j
        //即满足nums[i]-i>=nums[j]-j,子序列满足该值的升序
        int n = nums.size();
        vector<int> val(n);
        map<int,int> m;//离散化优先顺序
        for(int i=0;i<n;i++){
            val[i] = nums[i]-i;
            m[val[i]]++;
        }
        for(auto &[k,v]:m)
            v = idx++;
        for(auto &v:val)
            v = m[v];//用优先级替换数值

        tree.resize(idx+1,INT_MIN);
        long long res = INT_MIN;
        for(int i=0;i<n;i++){//找满足val更小的最大值
            int p = val[i];
            //找小于等于p的最大值
            long long premax = getmax(p);
            long long cur = premax+nums[i];
            res = max(res,cur);
            updata(p,cur);
        }
        return res;
    }

    int lowbit(int x){//求二进制化最后一位的值
        return x&(-x);
    }
    void updata(int i,long long k){ //
        while(i<=idx){//更新子树上所有值
            tree[i] = max(tree[i],k);
            i+=lowbit(i);//移动到父亲节点
        }
    }

    long long getmax(int i){  //求数组前i项的和
        long long res = 0;//比0大才加上
        while(i>0){//O(logn)求前缀和
            res = max(res,tree[i]);
            i-=lowbit(i);//移动到前一棵子树（子区间）
        }
        return res;
    }
};