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


  • 0
    C

    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) {
                    throw new IllegalArgumentException("badIndex");
                }
                
                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;
                    }
                    
                    return total;
                }
            }
        }
        
        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) {
                blocks.add(new Block(nums, start, end));
                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;
        }
    }
    

Log in to reply
 

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