题解 | 小红统计区间（hard）

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = 5;
            int k = 6;
            int[] a = new int[n];
            long[] sum = new long[n];
            long ans = 0;
            for (int i = 0; i < n; i ++ ) {
                sum[i] = (i == 0 ? 0 : sum[i - 1]) + a[i]; 
                long v = (i == 0 ? 0 : -sum[i - 1]);
                // tree 平衡二叉树
                tree.add(v);
                // 查询大于等于x的个数
                ans += tree.findLargerThanK(k - sum[i]);
            }

        }
    }

    // sum[i] += a[i]
    // tree.add(-sum[i - 1])
    // 此时tree里有i + 1个，每个元素+sum[i] ==> 从x点到j的元素和
    // 此时获取>= k - sum[i] 的个数
    // 重复循环
}