树状数组

• OI Wiki: https://oi-wiki.org/ds/fenwick/

题目	难度
307. 区域和检索 - 数组可修改	中等	单点更新，区间查询
315. 计算右侧小于当前元素的个数	困难	逆序对 见：离散化
剑指 Offer 51. 数组中的逆序对	困难	逆序对 见：离散化

思路

【宫水三叶】针对不同的题目，我们有不同的方案可以选择（假设我们有一个数组）：

1. 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
2. 多次修改某个数（单点），求区间和：「树状数组」、「线段树」
3. 多次修改某个区间，输出最终结果：「差分」
4. 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
5. 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）

这样看来，「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？

答案并不是，而且恰好相反，只有在我们遇到第 4 类问题，不得不写「线段树」的时候，我们才考虑线段树。

因为「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。

总结一下，我们应该按这样的优先级进行考虑：

1. 简单求区间和，用「前缀和」
2. 多次将某个区间变成同一个数，用「线段树」
3. 其他情况，用「树状数组」

307. 区域和检索 - 数组可修改

public class Solution307 {
    static class NumArray {
        private final Fenwick fenwick;

        public NumArray(int[] nums) {
            fenwick = new Fenwick(nums);
        }

        public void update(int index, int val) {
            int add = val - fenwick.getSum(index, index);
            fenwick.add(index + 1, add);
        }

        public int sumRange(int left, int right) {
            return fenwick.getSum(left, right);
        }

        private static class Fenwick {
            private final int n;
            private final int[] tree;

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

            // O(n) 建树
            public Fenwick(int[] nums) {
                this.n = nums.length;
                this.tree = new int[n + 1];
                for (int i = 1; i <= n; i++) {
                    tree[i] += nums[i - 1];
                    int j = i + lowbit(i);
                    if (j <= n) {
                        tree[j] += tree[i];
                    }
                }
            }

            int lowbit(int x) {
                return x & -x;
            }

            // nums[x] add k
            void add(int x, int k) {
                while (x <= n) {
                    tree[x] += k;
                    x += lowbit(x);
                }
            }

            // nums [1,x] 的和
            int getSum(int x) {
                int ans = 0;
                while (x > 0) {
                    ans += tree[x];
                    x -= lowbit(x);
                }
                return ans;
            }

            // nums [l,r] 的和
            int getSum(int l, int r) {
                return getSum(r + 1) - getSum(l);
            }
        }
    }
}

参考链接

• 【宫水三叶】关于各类「区间和」问题如何选择解决方案（含模板）

（全文完）