I’m learning the segment tree data structure but I cannot for the life of me figure out what’s wrong with my implementation. I’m using a 1-indexed tree, so nothing is stored at tree[0].

This means the root is at tree[1]. I make recursive calls using initial range 1 to n – 1, which I’m not sure about. I get different wrong answers when I make it go to self.n or start at 0. I also get different wrong answers if I pass in index+1, left+1 or right+1

Here is my implementation:

class NumArray:
    # Classic Segment Tree

    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * self.n * 2
        self.build(nums)

    def build(self, nums):
        # leaves
        for i in range(self.n):
            self.tree[i + self.n] = nums[i]

        # internal
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def merge(self, left, right):
        return left + right

    def _update(self, tree_idx, seg_left, seg_right, i, val):
        # leaf
        if seg_left == seg_right:
            self.tree[tree_idx] = val
            return

        mid = (seg_left + seg_right) // 2
        if i > mid:
            self._update(tree_idx * 2 + 1, mid + 1, seg_right, i, val)
        else:
            self._update(tree_idx * 2, seg_left, mid, i, val)

        self.tree[tree_idx] = self.merge(self.tree[tree_idx * 2], self.tree[tree_idx * 2 + 1])

    def update(self, index: int, val: int) -> None:
        self._update(1, 1, self.n - 1, index, val)

    def _sumRange(self, tree_idx, seg_left, seg_right, query_left, query_right):
        # segment out of query bounds
        if seg_left > query_right or seg_right < query_left:
            return 0

        # segment fully in bounds
        if seg_left >= query_left and seg_right <= query_right:
            return self.tree[tree_idx]

        # segment partially in bounds
        mid = (seg_left + seg_right) // 2

        # this is not necessary for correctness, but helps with efficiency (we only go down 1 path if 2 is unnecessary)
        if query_left > mid:
            return self._sumRange(tree_idx * 2 + 1, mid + 1, seg_right, query_left, query_right)
        elif query_right <= mid:
            return self._sumRange(tree_idx * 2, seg_left, mid, query_left, query_right)

        left_sum = self._sumRange(tree_idx * 2, seg_left, mid, query_left, query_right)
        right_sum = self._sumRange(tree_idx * 2 + 1, mid + 1, seg_right, query_left, query_right)

        return self.merge(left_sum, right_sum)

    def sumRange(self, left: int, right: int) -> int:
        return self._sumRange(1, 1, self.n - 1, left, right)

This website verifies if the segment tree implementation is correct