如何支持区间和多值的数据结构？

可以使用线段树作为数据结构来支持区间和多值操作。线段树是一种树形数据结构，用于解决一系列与区间、区间修改、区间查询等相关的问题。其基本思想是将区间分割成一些个体较小的子区间，并在这些子区间上建立二叉树，使得每个子区间对应线段树上的一个节点。线段树每个节点维护该区间的某个属性，如区间和、最大值、最小值等。

下面是线段树的代码示例：

class SegmentTree:
    def __init__(self, n, func):
        self.n = n
        self.tree = [0] * (2*n)
        self.func = func

    def build(self, arr):
        for i in range(self.n):
            self.tree[self.n+i] = arr[i]
        for i in range(self.n-1, 0, -1):
            self.tree[i] = self.func(self.tree[2*i], self.tree[2*i+1])

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.func(self.tree[2*i], self.tree[2*i+1])

    def query(self, l, r):
        l += self.n
        r += self.n+1
        res = 0
        while l < r:
            if l % 2 == 1:
                res = self.func(res, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.func(res, self.tree[r])
            l //= 2
            r //= 2
        return res

此外，若要支持多值操作，可以将线段树中的每个节点改为一个链表或者数组，存储多个值，然后在查询时将所有值合并即可。具体实现可以参考下面的代码：

class Node:
    def __init__(self, val):
        self.val = [val]
        self.next = None

class SegmentTreeMulti:
    def __init__(self, n):
        self.n = n
        self.tree = [Node(0)] * (2*n)

    def build(self, arr):
        for i in range(self.n):