class BinaryIndexedTree(object):

    def __init__(self):
        self.BITTree = [0]

    # Returns sum of arr[0..index]. This function assumes
    # that the array is preprocessed and partial sums of
    # array elements are stored in BITree[].
    def getsum(self, i):
        s = 0  # initialize result
        # index in BITree[] is 1 more than the index in arr[]
        i = i + 1
        # Traverse ancestors of BITree[index]
        while i > 0:
            # Add current element of BITree to sum
            s += self.BITTree[i]
            # Move index to parent node in getSum View
            i -= i & (-i)
        return s
    def get_sum(self, a, b):
        return self.getsum(b) - self.getsum(a-1) if a > 0 else 0
    # Updates a node in Binary Index Tree (BITree) at given index
    # in BITree. The given value 'val' is added to BITree[i] and
    # all of its ancestors in tree.
    def updatebit(self,  n, i, v):
        # index in BITree[] is 1 more than the index in arr[]
        i += 1

        # Traverse all ancestors and add 'val'
        while i <= n:
            # Add 'val' to current node of BI Tree
            self.BITTree[i] += v

            # Update index to that of parent in update View
            i += i & (-i)

        # Constructs and returns a Binary Indexed Tree for given


    # array of size n.
    def construct(self, arr, n):
        # Create and initialize BITree[] as 0
        self.BITTree = [0] * (n + 1)

        # Store the actual values in BITree[] using update()
        for i in range(n):
            self.updatebit(n, i, arr[i])


freq = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]

BITTree = BinaryIndexedTree()
BITTree.construct(freq,len(freq))
print("Sum of elements in arr[0..5] is " + str(BITTree.getsum(5)))
freq[3] += 6
BITTree.updatebit(len(freq), 3, 6)
print("Sum of elements in arr[0..5]"+
                    " after update is " + str(BITTree.getsum(5)))
print("Sum of elements in arr[1..5]"+
                    " after update is " + str(BITTree.get_sum(2, 5)))

class BinaryIndexedTree(object):

    def __init__(self):
        self.BITTree = [0]

    # Returns sum of arr[0..index]. This function assumes
    # that the array is preprocessed and partial sums of
    # array elements are stored in BITree[].
    def getsum(self, i):
        s = 0  # initialize result
        # index in BITree[] is 1 more than the index in arr[]
        i = i + 1
        # Traverse ancestors of BITree[index]
        while i > 0:
            # Add current element of BITree to sum
            s += self.BITTree[i]
            # Move index to parent node in getSum View
            i -= i & (-i)
        return s
    def get_sum(self, a, b):
        return self.getsum(b) - self.getsum(a-1) if a > 0 else 0
    # Updates a node in Binary Index Tree (BITree) at given index
    # in BITree. The given value 'val' is added to BITree[i] and
    # all of its ancestors in tree.
    def updatebit(self,  n, i, v):
        # index in BITree[] is 1 more than the index in arr[]
        i += 1

        # Traverse all ancestors and add 'val'
        while i <= n:
            # Add 'val' to current node of BI Tree
            self.BITTree[i] += v

            # Update index to that of parent in update View
            i += i & (-i)

        # Constructs and returns a Binary Indexed Tree for given


    # array of size n.
    def construct(self, arr, n):
        # Create and initialize BITree[] as 0
        self.BITTree = [0] * (n + 1)

        # Store the actual values in BITree[] using update()
        for i in range(n):
            self.updatebit(n, i, arr[i])


freq = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]

BITTree = BinaryIndexedTree()
BITTree.construct(freq,len(freq))
print("Sum of elements in arr[0..5] is " + str(BITTree.getsum(5)))
freq[3] += 6
BITTree.updatebit(len(freq), 3, 6)
print("Sum of elements in arr[0..5]"+
                    " after update is " + str(BITTree.getsum(5)))
print("Sum of elements in arr[1..5]"+
                    " after update is " + str(BITTree.get_sum(2, 5)))

# Returns sum of arr[0..index]. This function assumes # that the array is preprocessed and partial sums of # array elements are stored in BITree[]. # initialize result # index in BITree[] is 1 more than the index in arr[] # Traverse ancestors of BITree[index] # Add current element of BITree to sum # Move index to parent node in getSum View # Updates a node in Binary Index Tree (BITree) at given index # in BITree. The given value 'val' is added to BITree[i] and # all of its ancestors in tree. # index in BITree[] is 1 more than the index in arr[] # Traverse all ancestors and add 'val' # Add 'val' to current node of BI Tree # Update index to that of parent in update View # Constructs and returns a Binary Indexed Tree for given # array of size n. # Create and initialize BITree[] as 0 # Store the actual values in BITree[] using update()