from collections import deque


class Fenwick:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (self.n + 1)
        for index, value in enumerate(values):
            self.add(index, value)

    def add(self, index, delta):
        if not 0 <= index < self.n:
            raise IndexError(index)
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix(self, end):
        if not 0 <= end <= self.n:
            raise IndexError(end)
        answer = 0
        while end:
            answer += self.tree[end]
            end -= end & -end
        return answer

    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise IndexError((left, right))
        return self.prefix(right) - self.prefix(left)


def sliding_maximum(values, k):
    if not 1 <= k <= len(values):
        raise ValueError('k must be between 1 and len(values)')
    candidates, answer = deque(), []
    for i, value in enumerate(values):
        while candidates and candidates[0] <= i - k:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(i)
        if i >= k - 1:
            answer.append(values[candidates[0]])
    return answer


if __name__ == '__main__':
    sums = Fenwick([2, 1, 4, 3])
    print(sums.range_sum(1, 4))
    sums.add(2, 5)
    print(sums.range_sum(1, 4))
    print(sliding_maximum([1, 3, 2, 5, 4], 3))