[strongly recommend for beginners]clean C++ implementation with detailed explaination
Similiar C++ implementation based others'  posts.\n\nI have refered to the post from GeekForGeek\n\n[http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick
Similiar C++ implementation based others'  posts.\n\nI have refered to the post from GeekForGeek\n\n[http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/][1] \n\nI think the key points are that you should set "i++"  and understand the relationship of the children and parents.\n\n***THE KEY POINTS***\n\n\n***idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx \u2013 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx - 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).***\n\n***FOR EXAMPLE*** \n\n**Suppose we are looking for cumulative frequency of index 13 (for the first 13 elements). In binary notation, 13 is equal to 1101. Accordingly, we will calculate** \n\n      c[1101] = tree[1101] + tree[1100] + tree[1000] \n\n***HOW TO GET THE FINAL LAST SET BIT*** \n\nThere are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.\n\n     num=a1b\n\n    -num= (a1b)\xaf + 1 = a\xaf0b\xaf + 1\n\n    -num = (a1b)\xaf + 1 = a\xaf0b\xaf + 1 = a\xaf0(0\u20260)\xaf + 1 = a\xaf0(1\u20261) + 1 = a\xaf1(0\u20260) = a\xaf1b.\n\n b consists of all zeroes, so b\xaf consists of all ones. Finally we have\n\n    so the last set bit  :  00..1...00 = num & -num\n\n\nKey ideas -1-\n   **get-function-details**\n\n   getSum(index): Returns sum of arr[0..index]\n\n    // Returns sum of arr[0..index] using BITree[0..n].  It assumes that\n\n    // BITree[] is constructed for given array arr[0..n-1]\n\n     1) Initialize sum as 0 and index as index+1.\n\n     2) Do following while index is greater than 0.\n\n      ...a) Add BITree[index] to sum\n\n      ...b) Go to parent of BITree[index].  Parent can be obtained by removing\n\n             the last set bit from index, i.e., index = index - (index & (-index))\n\n     3) Return sum.\n\nKey ideas -2-   **update-value-function**  \n\n       update(index, val): Updates BIT for operation arr[index] += val\n\n       // Note that arr[] is not changed here.  It changes\n\n      // only BI Tree for the already made change in arr[].\n\n       1) Initialize index as index+1.\n\n       2) Do following while index is smaller than or equal to n.\n\n          ...a) Add value to BITree[index]\n\n          ...b) Go to parent of BITree[index].  Parent can be obtained by removing\n\n                 the last set bit from index, i.e., index = index + (index & (-index))\n\nHere is my final implementation.\n\n     class NumArray {\n        private:\n            vector<int> _nums;\n            vector<int> bit;\n            \n            int lower_bit(int i){\n                return i&-i;\n            }\n            \n            int query(int i){\n                i++;\n                int sum=0;\n                while(i>0){\n                    sum+=bit[i];\n                    i-=lower_bit(i);\n                }\n                return sum;\n            }\n            \n            void add(int i, int val){\n                i++;\n                while(i<bit.size()){\n                    bit[i]+=val;\n                    i+=lower_bit(i);\n                }\n            }\n            \n        public:\n            NumArray(vector<int> &nums) : _nums(nums) {\n                bit.resize(nums.size()+1);\n                for(int i=0; i<nums.size(); i++){\n                    add(i, nums[i]);\n                }\n            }\n        \n            void update(int i, int val) {\n                if(val!=_nums[i]){\n                    add(i, val-_nums[i]);\n                    _nums[i]=val;\n                }\n            }\n        \n            int sumRange(int i, int j) {\n                return query(j)-query(i-1);\n            }\n        };\n\n\n  [1]: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
[]