11 ms Java binary tree
public class NumArray {\n\n   \tint[] array;\n\tint size;\n    public NumArray(int[] nums) {\n        int len = nums.length;\n        size=1;\n        while(siz
public class NumArray {\n\n   \tint[] array;\n\tint size;\n    public NumArray(int[] nums) {\n        int len = nums.length;\n        size=1;\n        while(size<len)size=size*2;\n        array = new int[size*2-1];\n        for(int i=0;i<len;i++)array[size-1+i]=nums[i];\n        int ind = size*2-2;\n        while(ind>0){\n        \tarray[ind/2-1]=array[ind]+array[ind-1];\n        \tind=ind-2;\n        }\n    }\n\n    void update(int i, int val) {\n        int ind = i+size-1;\n        int delta = val - array[ind];\n        while(ind>0){\n        \tarray[ind]+=delta;\n        \tind = (ind-1)/2;\n        }\n        array[0]+=delta;\n    }\n\n    public int sumRange(int i, int j) {\n    \tint sumleft =0;\n    \tint ileft = size-1+i-1, len = i,u=1,bit;\n    \twhile(len>0){\n    \t\tbit = len&1;\n    \t\tif(bit==1){\n    \t\t\tsumleft+= array[(ileft - u +1 )/u];\n    \t\t\tileft = ileft -u;\n    \t\t}\n    \t\tu=u*2;\n    \t\tlen = len/2;\n    \t}\n    \tint sumright =0;\n    \tint iright = size-1+j+1;\n    \tlen = size - j -1;\n    \tu=1;\n    \twhile(len>0){\n    \t\tbit = len&1;\n    \t\tif(bit==1){\n    \t\t\tsumright+= array[iright/u];\n    \t\t\tileft = ileft +u;\n    \t\t}\n    \t\tu=u*2;\n    \t\tlen = len/2;\n    \t}\n        return array[0]-sumleft-sumright;\n    }\n}
[]