OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Why does my segment tree give incorrect answers?

  • Thread starter Thread starter Alec
  • Start date Start date
A

Alec

Guest
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:

Code:
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
<p>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 <code>tree[0]</code>.</p>
<p>This means the root is at <code>tree[1]</code>. 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</p>
<p>Here is my implementation:</p>
<pre class="lang-py prettyprint-override"><code>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

# internal
for i in range(self.n - 1, 0, -1):
self.tree = 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)

</code></pre>
<p><a href="https://leetcode.com/problems/range-sum-query-mutable/" rel="nofollow noreferrer">This website</a> verifies if the segment tree implementation is correct</p>
 

Latest posts

ن
Replies
0
Views
1
نعمان منذر محمود الجميلي
ن
Top