以下是 LeetCode 1649「通过指令创建有序数组」的 Java 解法，采用树状数组（Fenwick Tree）统计小于和大于当前数字的已插入元素个数，时间复杂度 O(n log M)，空间复杂度 O(M)，其中 M 为指令数值范围（题目给定 ≤ 10^5）。

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MAX_VAL = 100_000;   // 根据题目约束，instructions[i] ≤ 100000

    public int createSortedArray(int[] instructions) {
        FenwickTree bit = new FenwickTree(MAX_VAL);
        long totalCost = 0L;

        for (int i = 0; i < instructions.length; i++) {
            int x = instructions[i];
            int less = bit.query(x - 1);          // 小于 x 的元素个数
            int greater = i - bit.query(x);       // 大于 x 的元素个数 = 已插入总数 - 小于等于 x 的个数
            totalCost += Math.min(less, greater);
            bit.update(x, 1);
        }

        return (int) (totalCost % MOD);
    }

    // 树状数组（Fenwick Tree）
    class FenwickTree {
        private int n;
        private int[] tree;

        public FenwickTree(int n) {
            this.n = n;
            this.tree = new int[n + 2];
        }

        // 单点更新：位置 index 增加 delta
        public void update(int index, int delta) {
            while (index <= n) {
                tree[index] += delta;
                index += index & -index;
            }
        }

        // 前缀查询：返回 [1, index] 的累加和
        public int query(int index) {
            int sum = 0;
            while (index > 0) {
                sum += tree[index];
                index -= index & -index;
            }
            return sum;
        }
    }
}

核心思路

1. 使用树状数组维护每个数值的出现次数，支持 O(log M) 的前缀和查询与单点更新。
2. 遍历指令数组时，对于当前数字 x：
   • less = bit.query(x - 1) 得到严格小于 x 的元素个数。
   • greater = i - bit.query(x)，其中 i 是已插入的总元素数，bit.query(x) 是小于等于 x 的元素个数，相减即得大于 x 的元素个数。
3. 将 min(less, greater) 累加到总成本，最后对 MOD 取模返回。

复杂度分析

• 时间复杂度：O(n log M)，n 为指令数组长度，M = 10^5。
• 空间复杂度：O(M)。