树状数组

static class FenwickTree {
        int[] arr;
        int[] b;
        int n;

        public FenwickTree(int[] nums) {
            this.arr = nums;
            n = nums.length;
            init(nums);
        }

        private void init(int[] nums) {
            b = new int[n + 1];
            for(int i = 1;i <= nums.length;i++) {
                int k = i;
                while(k <= n) {
                    b[k] += nums[i - 1];
                    k += (k & -k);
                }
            }
        }

        public void update(int i, int val) {
            int tmp = arr[i];
            arr[i] = val;
            int k = i + 1;
            while(k <= n) {
                b[k] -= tmp;
                b[k] += val;
                k += (k & -k);
            }
        }

        public int sum(int l, int r) {
            return sum(r + 1) - sum(l);
        }

        private int sum(int r) {
            int sum = 0;
            while(r > 0) {
                sum += b[r];
                r -= (r & -r);
            }

            return sum;
        }
    }