第3天补记10单，为什么累计表不必从第3天一路改到最后？

"""Point increments and prefix sums with visible Fenwick coverage."""
import itertools
import json


class Fenwick:
    def __init__(self, values):
        values = tuple(values)
        if len(values) > 10000 or any(type(x) is not int for x in values):
            raise ValueError("at most 10000 integer entries")
        self.n = len(values)
        self.tree = [0] * (self.n + 1)
        for i, value in enumerate(values, 1):
            self.add(i, value)

    def add(self, index, delta):
        if type(index) is not int or not 1 <= index <= self.n or type(delta) is not int:
            raise ValueError("one-based index in range and integer delta required")
        touched = []
        while index <= self.n:
            self.tree[index] += delta
            touched.append(index)
            index += index & -index
        return touched

    def prefix(self, count):
        if type(count) is not int or not 0 <= count <= self.n:
            raise ValueError("prefix count outside 0..n")
        total, visited = 0, []
        while count:
            total += self.tree[count]
            visited.append(count)
            count -= count & -count
        return total, visited

    def range_sum(self, left, right):
        if any(type(x) is not int for x in (left, right)) or not 1 <= left <= right <= self.n:
            raise ValueError("inclusive range requires 1 <= left <= right <= n")
        return self.prefix(right)[0] - self.prefix(left - 1)[0]


def main():
    checks, cases = 0, 0
    def check(ok):
        nonlocal checks
        if not ok:
            raise AssertionError("Fenwick check failed")
        checks += 1

    for n in range(6):
        for values in itertools.product((-1, 0, 2), repeat=n):
            tree = Fenwick(values)
            # Oracle scans raw values, never uses lowbit or tree coverage.
            for r in range(n + 1):
                check(tree.prefix(r)[0] == sum(values[:r]))
            for i in range(1, n + 1):
                for delta in (-3, 4):
                    changed = list(values)
                    changed[i - 1] += delta
                    touched = tree.add(i, delta)
                    for r in range(n + 1):
                        check(tree.prefix(r)[0] == sum(changed[:r]))
                    for left in range(1, n + 1):
                        for right in range(left, n + 1):
                            check(tree.range_sum(left, right) == sum(changed[left-1:right]))
                    check(len(touched) == len(set(touched)))
                    tree.add(i, -delta)
            cases += 1
    demo = Fenwick([3, 1, 4, 1, 5, 9, 2, 6])
    before = demo.prefix(7)
    touched = demo.add(3, 10)
    after = demo.prefix(7)
    check(before == (25, [7, 6, 4]))
    check(after == (35, [7, 6, 4]))
    check(touched == [3, 4, 8])
    check(Fenwick(iter([1, 2])).prefix(2)[0] == 3)
    invalid = [lambda: demo.add(0, 1), lambda: demo.add(True, 1),
               lambda: demo.add(9, 1), lambda: demo.prefix(-1),
               lambda: demo.range_sum(3, 2), lambda: Fenwick([False])]
    for action in invalid:
        try:
            action()
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid operation accepted")
    print(json.dumps({"checks_passed": checks, "exhaustive_initial_arrays": cases,
                      "prefix_7_before": before, "add_10_at_3_touched": touched,
                      "prefix_7_after": after, "tree_after": demo.tree,
                      "scope": "one-based point increments; inclusive range sums; integers; no concurrent updates"}, indent=2))


if __name__ == "__main__":
    main()