Segment Tree

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

search and update: O(log n)

public class NumArray {
    class TreeNode {
        int start;
        int end;
        int sum;

        TreeNode left;
        TreeNode right;

        public TreeNode(int s, int e, int sum) {
            this.start = s;
            this.end = e;
            this.sum = sum;
        }
    }

    private int[] nums;
    private TreeNode root;

    public NumArray(int[] nums) {
        this.nums = nums;

        if (nums.length > 0) {
            root = buildTree(0, nums.length - 1);
        }
    }

    public void update(int i, int val) {
        if (i >= nums.length || i < 0) return;

        root = updateTree(root, i, val);
    }

    public int sumRange(int i, int j) {
        return getRangeSum(root, i, j);
    }

    private TreeNode buildTree(int start, int end) {
        TreeNode node = new TreeNode(start, end, 0);

        if (start == end) {
            node.sum = nums[start];
            return node;
        }

        int mid = start + (end - start) / 2;

        TreeNode left = buildTree(start, mid);
        TreeNode right = buildTree(mid + 1, end);

        node.sum = left.sum + right.sum;

        node.left = left;
        node.right = right;
        return node;
    }

    private int getRangeSum(TreeNode node, int i, int j) {
        //not overlapped 
        if (node == null) return 0;
        if (node.end < i || node.start > j) return 0;
        if (node.end <= j && node.start >= i) return node.sum;

        int left = getRangeSum(node.left, i, j);
        int right = getRangeSum(node.right, i, j);

        return left + right;
    }

    private TreeNode updateTree(TreeNode node, int i, int val) {

        if (node == null) return null;

        if (node.start > i || node.end < i) {
            return node;
        }

        if (node.start == node.end && node.start == i) {
            node.sum = val;
            return node;
        }

        TreeNode left = updateTree(node.left, i, val);
        TreeNode right = updateTree(node.right, i, val);

        int sum = 0;
        if (left != null) sum += left.sum;
        if (right != null) sum += right.sum;

        if (node.sum != sum) node.sum = sum;

        return node;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */