returns the right most significant bit of an integer for example 12 is represented by 1100 in binary so it s lsb is the third position 4 a fenwick tree allows you to sum a range of elements and update an element in an array in ologn a segment tree can also achieve this but it takes twice the memory making it less memory efficient on the other hand a segment tree can compute more functions in a range of elements like the minimum or maximum the way it works is that given an index note that we start with 1 and not 0 the element in the array will be the sum of the lsbindex elements below including index for example with index 3 3 11 in binary and lsb3 1 so this element is equal to the corresponding element in the original array but 4 100 in binary so lsb4 4 so it is equal to the sum of a0 a1 a2 a3 the first 4 elements of the original array initialize an array of length n1 to 0 update the array to the one passed in the parameters update the value for every element that sums aindex get the sum of all elements before index included get the sum of all elements in the range start end returns the right most significant bit of an integer for example 12 is represented by 1100 in binary so it s lsb is the third position 4 a fenwick tree allows you to sum a range of elements and update an element in an array in o log n a segment tree can also achieve this but it takes twice the memory making it less memory efficient on the other hand a segment tree can compute more functions in a range of elements like the minimum or maximum the way it works is that given an index note that we start with 1 and not 0 the element in the array will be the sum of the lsb index elements below including index for example with index 3 3 11 in binary and lsb 3 1 so this element is equal to the corresponding element in the original array but 4 100 in binary so lsb 4 4 so it is equal to the sum of a 0 a 1 a 2 a 3 the first 4 elements of the original array initialize an array of length n 1 to 0 update the array to the one passed in the parameters update the value for every element that sums a index get the sum of all elements before index included get the sum of all elements in the range start end
def LSB(n):
    return n & -n


class FenwickTree:
    

    def __init__(self, array):
        self.len = len(array)+1
        
        self.arr = [0] * self.len
        
        for i in range(0, self.len - 1):
            self.update(i, array[i])

    def update(self, index, val):
        j = index+1
        
        while j < self.len:
            self.arr[j] += val
            j += LSB(j)

    
    def get_sum(self, index):
        sum = 0
        index += 1
        while index > 0:
            sum += self.arr[index]
            index -= LSB(index)
        return sum

    
    def get_sum_range(self, start, end):
        return self.get_sum(end) - self.get_sum(start-1)


if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5, 6, 7, 8]
    fw = FenwickTree(arr)
    print(fw.get_sum(3))
    print(fw.get_sum(5))
    print(fw.get_sum_range(1, 7))