بنيتا Fenwick وشجرة المقاطع للمجالات

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 ValueError("Invalid element index")
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
    def prefix(self, end):
        if not 0 <= end <= self.n:
            raise ValueError("Invalid prefix end")
        total, i = 0, end
        while i:
            total += self.tree[i]
            i -= i & -i
        return total
    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise ValueError("Invalid half-open range")
        return self.prefix(right) - self.prefix(left)

tree = Fenwick([4, -2, 5, 1])
print(tree.range_sum(1, 3))
tree.add(1, 3)
print(tree.range_sum(1, 3))
print(tree.range_sum(0, 4))

3
6
11

تغير إضافة 3 القيمة الثانية من -2 إلى 1. وتظل فروق المجاميع السابقة صحيحة بعد إصلاح التجميعات بعدد لوغاريتمي من الخطوات.

class SegmentSum:
    def __init__(self, values):
        self.n = len(values)
        self.base = 1
        while self.base < self.n:
            self.base *= 2
        self.tree = [0] * (2 * self.base)
        self.tree[self.base:self.base + self.n] = values
        for i in range(self.base - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    def assign(self, index, value):
        if not 0 <= index < self.n:
            raise ValueError("Invalid element index")
        i = self.base + index
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise ValueError("Invalid half-open range")
        left += self.base
        right += self.base
        total = 0
        while left < right:
            if left & 1:
                total += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                total += self.tree[right]
            left //= 2
            right //= 2
        return total

tree = SegmentSum([4, -2, 5, 1])
print(tree.range_sum(1, 3))
tree.assign(1, 1)
print(tree.range_sum(1, 3))
print(tree.range_sum(0, 4))

3
6
11

يطابق الإسناد إلى 1 إضافة delta=3 في المثال الأول فقط لأن القيمة القديمة كانت -2. تكشف الواجهتان معنيين مختلفين للتحديث عن قصد.