# Square root decomposition solution, although it's not the fastest at O(sqrt(n)) ~ 150ms

• Here's a solution I came up with in Java to practice and demonstrate the square root decomposition technique. This might have wider applicability than, for instance, a binary indexed tree, although it has a runtime complexity of O(sqrt(n)).

``````class NumArray {

static class Block {
int[] nums;
int start = 0;
int end = 0;
int sum = 0;

public Block(int[] nums, int start, int end) {
this.nums = nums;
this.start = start;
if (end > nums.length) {
end = nums.length;
}
this.end = end;

for (; start < end; ++start) {
this.sum += nums[start];
}
}

public void update(int index, int val) {
if (index < start || index >= end) {
}

int diff = val - nums[index];
sum += diff;
nums[index] = val;
}

public int sumRange(int i, int j) {
if (i > end || j < start) {
return 0;
} else if (i < start && j > end) {
return sum;
} else {
i = Math.max(i, start);
j = Math.min(j, end);

int total = 0;
while (i < j) {
total += nums[i];
++i;
}

}
}
}

List<Block> blocks;
int blockSize;

public NumArray(int[] nums) {
blockSize = ((int)Math.sqrt(nums.length));

blocks = new ArrayList<>();

int start = 0;
int end = blockSize;

while (start < nums.length) {
start = end;
end += blockSize;
}

}

public void update(int i, int val) {
Block block = blocks.get(whichBlock(i));
block.update(i, val);
}

public int sumRange(int i, int j) {
++j; // I prefer j to be exclusive

int sum = 0;
int blockIndex = whichBlock(i);

while(blockIndex * blockSize < j) {
Block block = blocks.get(blockIndex);
sum += block.sumRange(i, j);
++blockIndex;
}
return sum;
}

public int whichBlock(int index) {
return index / blockSize;
}
}
``````

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