力扣1649题解：高效计算有序数组插入代价的树状数组解法

一、问题分析

这道题目要求我们计算将一个数组中的元素依次插入到一个初始为空的数组中时，所有插入操作的总代价。每次插入的代价定义为：

• 当前数组中严格小于插入元素的数目

• 当前数组中严格大于插入元素的数目
  两者中的较小值

二、解题思路

我们可以使用树状数组(Fenwick Tree)来高效解决这个问题：

1. 离散化处理所有可能的数值

2. 使用树状数组维护当前数组中各数字的出现次数

3. 对于每个插入元素，快速查询小于和大于它的元素数量

4. 计算每次插入的代价并累加

三、C++代码实现

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 1) {}
    
    void update(int index, int delta) {
        while (index < tree.size()) {
            tree[index] += delta;
            index += index & -index;
        }
    }
    
    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
};

class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        const int MOD = 1e9 + 7;
        // 离散化处理
        vector<int> sorted = instructions;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        
        FenwickTree ft(sorted.size());
        int totalCost = 0;
        
        for (int num : instructions) {
            // 获取离散化后的索引
            int rank = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;
            // 查询小于当前数的数量
            int less = ft.query(rank - 1);
            // 查询小于等于当前数的数量
            int lessEqual = ft.query(rank);
            // 当前数的出现次数
            int same = lessEqual - less;
            // 大于当前数的数量 = 总数 - 小于等于的数量
            int greater = ft.query(sorted.size()) - lessEqual;
            
            // 计算当前插入代价
            int cost = min(less, greater);
            totalCost = (totalCost + cost) % MOD;
            
            // 更新树状数组
            ft.update(rank, 1);
        }
        
        return totalCost;
    }
};

四、代码详解

1. ‌FenwickTree类‌：

• 实现了树状数组的基本操作：update和query

• update用于更新某个位置的值

• query用于查询前缀和

2. ‌离散化处理‌：

• 对输入数组进行排序和去重

• 将原始数值映射到连续的索引

3. ‌主逻辑‌：

• 遍历instructions数组

• 对每个元素查询小于和大于它的数量

• 计算当前插入代价并累加

• 更新树状数组

4. ‌复杂度分析‌：

• 时间复杂度：O(n log n)，其中n是instructions的长度

• 空间复杂度：O(n)，用于存储离散化后的数组和树状数组

五、算法优化

1. ‌离散化优化‌：

• 通过排序和去重减少树状数组的大小

• 使用二分查找快速定位元素位置

2. ‌树状数组优势‌：

• 查询和更新操作都是O(log n)复杂度

• 比直接维护有序数组更高效

六、扩展思考

1. 如果允许重复元素，算法需要做哪些调整？

2. 如何修改算法来处理插入代价定义为两者之和而非较小值？

3. 如果instructions非常大，如何进一步优化空间复杂度？

掌握这种树状数组解法，能够帮助你解决许多类似的动态规划和查询问题！