315 Count of smaller numbers after self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

关键在于从brute force的insight中提炼出其实就是看某个range里的总数，并且是在build tree的过程中实时去看

再归根结底，关键是搞明白segment tree基于的range数组到底是什么，数组里面的数代表什么，每个数的index又是什么，这有时候很关键有时候很隐晦

注意range数组的range最好是从非负数开始，否则会出毛病

class Solution {
    private int offset = 10000;
    private int MAXN = 20001;
    // segment tree，range就是最大值到最小值，只是加上了offset来避免负数下标
    // 这个没办法再reduce是因为把val排序去重最后的最大range也不会改变
    private int[] counts = new int[MAXN*4];
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        // 从右往左积累cnt，然后数右边已经看过了的中小于自己的总数
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i];
            increase(num+offset, 0, offset*2, 1);
            int cnt = query(0, num+offset-1, 0, offset*2, 1);
            ans.add(cnt);
        }
        Collections.reverse(ans);
        return ans;
    }
    private void increase(int val, int left, int right, int idx) {
        if (val == left && val == right) {
            counts[idx]++;
            return;
        }
        int mid = (left + right) / 2;
        if (val <= mid) {
            increase(val, left, mid, idx*2);
        }
        if (val > mid) {
            increase(val, mid+1, right, idx*2+1);
        }
        counts[idx] = counts[idx*2]+counts[idx*2+1];
    }
    private int query(int jobl, int jobr, int left, int right, int idx) {
        // hmm, 以后还是得加上这一句
        if (jobr < left || jobl > right) {
            return 0;
        }
        if (left >= jobl && right <= jobr) {
            return counts[idx];
        }
        int mid = (left + right) / 2;
        int cntl = 0;
        int cntr = 0;
        if (jobl <= mid) {
            cntl = query(jobl, jobr, left, mid, idx*2);
        }
        if (jobr > mid) {
            cntr = query(jobl, jobr, mid+1, right, idx*2+1);
        }
        return cntl + cntr;
    }
}