Fenwick tree Golang solution


  • 0
    N
    type NumArray struct {
    	nums []int
    	fenwicktree []int
    }
    
    
    func Constructor(nums []int) NumArray {
    	fenwicktree := make([]int, len(nums) + 1)
    
    	for i := 1; i <= len(nums); i++ {
    		range_start := i - (i & (-i)) + 1
    		for j := range_start; j <= i; j++ {
    			fenwicktree[i] += nums[j - 1]
    		}
    	}
    
    	return NumArray{nums, fenwicktree}
    }
    
    
    func (this *NumArray) Update(i int, val int)  {
    	adjust := val - this.nums[i]
    	this.nums[i] = val
    	i += 1
    	for ;i < len(this.fenwicktree); i += (i & (-i)) {
    		this.fenwicktree[i] += adjust
    	}
    }
    
    
    func (this *NumArray) SumRange(i int, j int) int {
    	s1 := 0
    	s2 := 0
    
    	for ;i > 0; i -= (i & (-i)) {
    		s1 += this.fenwicktree[i]
    	}
    
    	j += 1
    	for ;j > 0; j -= (j & (-j)) {
    		s2 += this.fenwicktree[j]
    	}
    
    	return s2 - s1
    }
    

Log in to reply
 

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