Segment Tree vs Binary Indexed Tree
Segment Tree\n\nclass NumArray {\n    private int[] lo, hi, sum;\n    \n    private int n;\n    private int[] nums;\n    public NumArray(int[] nums) {\n        
### Segment Tree\n```\nclass NumArray {\n    private int[] lo, hi, sum;\n    \n    private int n;\n    private int[] nums;\n    public NumArray(int[] nums) {\n        if (nums.length == 0)\n            return;\n        \n        n = nums.length;\n        this.nums = nums;\n        \n        lo = new int[4 * n + 1];\n        hi = new int[4 * n + 1];\n        sum = new int[4 * n + 1];\n        \n        init(1, 0, n - 1);\n    }\n    \n    private int init(int nodei, int l, int h) {\n        lo[nodei] = l;\n        hi[nodei] = h;\n        \n        if (l == h) {\n            return sum[nodei] = nums[l];\n        } else {\n            int left = init(2 * nodei, l, (l + h) / 2);\n            int right = init(2 * nodei + 1, (l + h) / 2 + 1, h);\n            return sum[nodei] = left + right;\n        }\n    }\n    \n    public void update(int i, int val) {\n        updateUtil(1, i, val - nums[i]);\n        nums[i] = val;\n    }\n    \n    private void updateUtil(int nodei, int i, int diff) {\n        if (nodei < 4 * n + 1 && lo[nodei] <= i && i <= hi[nodei]) {\n            sum[nodei] += diff;\n            updateUtil(2 * nodei, i, diff);\n            updateUtil(2 * nodei + 1, i, diff);\n        }\n    }\n    \n    public int sumRange(int i, int j) {\n        return sumRangeUtil(1, i, j);\n    }\n\n    private int sumRangeUtil(int nodei, int l, int h) {\n        if (h < lo[nodei] || l > hi[nodei]) {\n            return 0;\n        } else if (l <= lo[nodei] && hi[nodei] <= h) {\n            return sum[nodei];\n        }\n\n        int sumLeft = sumRangeUtil(2 * nodei, l, h);\n        int sumRight = sumRangeUtil(2 * nodei + 1, l, h);\n\n        return sumLeft + sumRight;\n    }\n}\n```\n\n### Binary Indexed Tree\n```\nclass NumArray {\n    private BinaryIndexedTree bit;\n    private int[] nums;\n    \n    public NumArray(int[] nums) {\n        this.nums = nums;\n        bit = new BinaryIndexedTree(nums);\n    }\n    \n    public void update(int i, int val) {\n        bit.update(i + 1, val - nums[i]);\n        nums[i] = val;\n    }\n    \n    public int sumRange(int i, int j) {\n        return bit.query(j + 1) - bit.query(i);\n    }\n}\n\nclass BinaryIndexedTree {\n    private int[] sum;\n\n    public BinaryIndexedTree(int[] nums) {\n        sum = new int[nums.length + 1];\n        for (int i = 0; i < nums.length; i++) {\n            update(i + 1, nums[i]);\n        }\n    }\n\n    public void update(int i, int delta) {\n        while (i < sum.length) {\n            sum[i] += delta;\n            i += lowbit(i);\n        }\n    }\n\n    public int query(int i) {\n        int s = 0;\n        while (i > 0) {\n            s += sum[i];\n            i -= lowbit(i);\n        }\n        return s;\n    }\n\n    private int lowbit(int x) {\n        return x & (~x + 1);\n    }\n}\n```\n
['Tree', 'Binary Indexed Tree']