# Binary Indexed Tree (Fenwick Tree) solution in Java (Fenwick Tree tutorial link included)

``````/*
binary indexed tree (fenwick tree) approach.

input: array in[] of size n
we make: cumulative frequency array tree[] of size n + 1. tree[0] = 0.
-- "initialize" can be treated as "update from 0 to nums[i]".
-- update(i, diff)
while (i <= n) {
tree[i] += diff;
i += (i & -i);
}
-- cumulativeSum(i)
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= (i & -i);
}
return sum;
--sumRange(i, j)
return cumulativeSum(j) - cumulativeSum(i - 1);
*/
public class NumArray {

int[] tree;  // (partial) cumulative frequency array of size n + 1
int[] numsCopy;  // a copy of the original array nums

private void updateHelper(int idx, int diff) {
while (idx <= numsCopy.length) {
tree[idx] += diff;
idx += (idx & -idx);
}
}

private int cumulativeSum(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}

public NumArray(int[] nums) {
if (nums != null) {
numsCopy = new int[nums.length];
for (int i = 0; i < nums.length; ++i) numsCopy[i] = nums[i];
tree = new int[nums.length + 1];  // partial cumulative sum (binary indexed)
for (int i = 0; i < nums.length; ++i) updateHelper(i + 1, nums[i]);
}
}

void update(int i, int val) {
updateHelper(i + 1, val - numsCopy[i]);
numsCopy[i] = val;
}

public int sumRange(int i, int j) {
return cumulativeSum(j + 1) - cumulativeSum(i);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.