Java using Binary Indexed Tree with clear explanation
This is to share the explanation of the BIT and the meaning of the bit operations.\n\n    public class NumArray {\n\t\t/\n\t\t * Binary Indexed Trees (BIT or Fe
This is to share the explanation of the BIT and the meaning of the bit operations.\n\n    public class NumArray {\n\t\t/**\n\t\t * Binary Indexed Trees (BIT or Fenwick tree):\n\t\t * https://www.topcoder.com/community/data-science/data-science-\n\t\t * tutorials/binary-indexed-trees/\n\t\t * \n\t\t * Example: given an array a[0]...a[7], we use a array BIT[9] to\n\t\t * represent a tree, where index [2] is the parent of [1] and [3], [6]\n\t\t * is the parent of [5] and [7], [4] is the parent of [2] and [6], and\n\t\t * [8] is the parent of [4]. I.e.,\n\t\t * \n\t\t * BIT[] as a binary tree:\n\t\t *            ______________*\n\t\t *            ______*\n\t\t *            __*     __*\n\t\t *            *   *   *   *\n\t\t * indices: 0 1 2 3 4 5 6 7 8\n\t\t * \n\t\t * BIT[i] = ([i] is a left child) ? the partial sum from its left most\n\t\t * descendant to itself : the partial sum from its parent (exclusive) to\n\t\t * itself. (check the range of "__").\n\t\t * \n\t\t * Eg. BIT[1]=a[0], BIT[2]=a[1]+BIT[1]=a[1]+a[0], BIT[3]=a[2],\n\t\t * BIT[4]=a[3]+BIT[3]+BIT[2]=a[3]+a[2]+a[1]+a[0],\n\t\t * BIT[6]=a[5]+BIT[5]=a[5]+a[4],\n\t\t * BIT[8]=a[7]+BIT[7]+BIT[6]+BIT[4]=a[7]+a[6]+...+a[0], ...\n\t\t * \n\t\t * Thus, to update a[1]=BIT[2], we shall update BIT[2], BIT[4], BIT[8],\n\t\t * i.e., for current [i], the next update [j] is j=i+(i&-i) //double the\n\t\t * last 1-bit from [i].\n\t\t * \n\t\t * Similarly, to get the partial sum up to a[6]=BIT[7], we shall get the\n\t\t * sum of BIT[7], BIT[6], BIT[4], i.e., for current [i], the next\n\t\t * summand [j] is j=i-(i&-i) // delete the last 1-bit from [i].\n\t\t * \n\t\t * To obtain the original value of a[7] (corresponding to index [8] of\n\t\t * BIT), we have to subtract BIT[7], BIT[6], BIT[4] from BIT[8], i.e.,\n\t\t * starting from [idx-1], for current [i], the next subtrahend [j] is\n\t\t * j=i-(i&-i), up to j==idx-(idx&-idx) exclusive. (However, a quicker\n\t\t * way but using extra space is to store the original array.)\n\t\t */\n\n\t\tint[] nums;\n\t\tint[] BIT;\n\t\tint n;\n\n\t\tpublic NumArray(int[] nums) {\n\t\t\tthis.nums = nums;\n\n\t\t\tn = nums.length;\n\t\t\tBIT = new int[n + 1];\n\t\t\tfor (int i = 0; i < n; i++)\n\t\t\t\tinit(i, nums[i]);\n\t\t}\n\n\t\tpublic void init(int i, int val) {\n\t\t\ti++;\n\t\t\twhile (i <= n) {\n\t\t\t\tBIT[i] += val;\n\t\t\t\ti += (i & -i);\n\t\t\t}\n\t\t}\n\n\t\tvoid update(int i, int val) {\n\t\t\tint diff = val - nums[i];\n\t\t\tnums[i] = val;\n\t\t\tinit(i, diff);\n\t\t}\n\n\t\tpublic int getSum(int i) {\n\t\t\tint sum = 0;\n\t\t\ti++;\n\t\t\twhile (i > 0) {\n\t\t\t\tsum += BIT[i];\n\t\t\t\ti -= (i & -i);\n\t\t\t}\n\t\t\treturn sum;\n\t\t}\n\n\t\tpublic int sumRange(int i, int j) {\n\t\t\treturn getSum(j) - getSum(i - 1);\n\t\t}\n\t}\n\n\t// Your NumArray object will be instantiated and called as such:\n\t// NumArray numArray = new NumArray(nums);\n\t// numArray.sumRange(0, 1);\n\t// numArray.update(1, 10);\n\t// numArray.sumRange(1, 2);
['Binary Tree', 'Java']