用途

树状数组主要用来求解前缀和、区间和、逆序对、区间和的个数和相关求个数的问题等等问题，最重要的是要考虑怎么将题目给的信息转化为一个前缀和，这一点是比较难想到的。

模板

int[] tr;
int n;

public int lowbit(int i) {
    return i & -i;
}

public void add(int i, int k) {
    for (; i <= n; i += lowbit(i))
        tr[i] += k;
}

public int sum(int i) {
    int res = 0;
    for (; i > 0; i -= lowbit(i))
        res += tr[i];
    return res;
}

n就是原数组，初始化时 tr = new int[n + 1];
当然也可以将这些变量和方法封装到一个类中，方便重复使用，不过一般的树状数组的问题只需要一个树状数组即可。

离散化

离散化就是当数据个数较少但比较分散并且我们只关心相对大小时，将他们的值分别映射到区间[1, N]，这样就可以依赖树状数组来处理数据了。

// 离散化、去重
TreeSet<Long> set = new TreeSet<>();
HashMap<Long, Integer> map = new HashMap<>();
for (int i = 0; i <= nums.length; i++) {
    set.add(preSum[i]);
    set.add(preSum[i] - lower);
    set.add(preSum[i] - upper);
}
int idx = 1;
for (Long num : set) {
    map.put(num, idx++);
}

要注意映射后的左端点为1，这样可以方便树状数组操作，树状数组的sum(i)方法就表示 目标值小于等于i的前缀和，通过该sum方法做减法、求最值、比较大小等等就可以方便的求出一些特定问题。
另外，排序也可以直接映射，不过java中没有unique方法，无法去重。去重的步骤可以提高效率，不影响正确性。