https://leetcode.cn/problems/create-sorted-array-through-instructions/solution/cpython3-dan-dian-geng-xin-1shu-zhuang-s-ktcj/

<aside> ⚠️ 似乎这两个模板都不能实现区间更新

</aside>

线段树数组实现模板

class SegmentTree:
    def __init__(self, n: int):
        # [0, n-1]
        self.treesum = [0 for _ in range(4 * n)]
        self.n = n

    def update(self, i: int, diff: int) -> None:
        return self._update(0, 0, self.n - 1, i, diff)
    
    def query(self, ql: int, qr: int) -> int:
        # [ql, qr]
        return self._query(0, 0, self.n - 1, ql, qr)

    def _update(self, root: int, l: int, r: int, ID: int, diff: int) -> int:
        if l == r == ID:
            self.treesum[root] += diff
            # self.treesum[root] = diff  若想要设置值而不是累加，改这里
            return 
        left = 2 * root + 1
        right = 2 * root + 2
        mid = (l + r) // 2
        if ID <= mid:
            self._update(left, l, mid, ID, diff)
        else:
            self._update(right, mid + 1, r, ID, diff)
        self.treesum[root] = self.treesum[left] + self.treesum[right]
    
    def _query(self, root: int, l: int, r: int, ql: int, qr: int) -> int:
        if ql == l and r == qr:
            return self.treesum[root]
        left = 2 * root + 1
        right = 2 * root + 2
        mid = (l + r) // 2
        if qr <= mid:
            return self._query(left, l, mid, ql, qr)
        elif mid + 1 <= ql:
            return self._query(right, mid + 1, r, ql, qr)
        else:
            return self._query(left, l, mid, ql, mid) + self._query(right, mid + 1, r, mid + 1, qr)

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = max(instructions)
        ST = SegmentTree(n + 1)
        res = 0
        for x in instructions:
            lesser = ST.query(1, x - 1) if 1 <= x-1 else 0
            greater = ST.query(x + 1, n) if x+1 <= n else 0
            res += min(lesser, greater)
            res %= MOD
            ST.update(x, 1)
        return res

作者：XingHe_XingHe
链接：<https://leetcode.cn/problems/create-sorted-array-through-instructions/solution/cpython3-dan-dian-geng-xin-1shu-zhuang-s-ktcj/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

求区间最小值版本

class SegmentTreeMin:
	def __init__(self, n: int):
		self.treesum = [0 for _ in range(4 * n)]
		self.n = n
		
	def update(self, i: int, diff: int) -> None:
		return self._update(0, 0, self.n - 1, i, diff)
	
	def query(self, ql: int, qr: int) -> int:
		return self._query(0, 0, self.n - 1, ql, qr)
	
	def _update(self, root: int, l: int, r: int, ID: int, diff: int) -> int:
		if l == r == ID:
      self.treesum[root] += diff
			# self.treesum[root] = diff
			return 
		left = 2 * root + 1
		right = 2 * root + 2
		mid = (l + r) // 2
		if ID <= mid:
			self._update(left, l, mid, ID, diff)
		else:
			self._update(right, mid + 1, r, ID, diff)
		self.treesum[root] = min(self.treesum[left], self.treesum[right]) # here
		
	def _query(self, root: int, l: int, r: int, ql: int, qr: int) -> int:
		if ql == l and r == qr:
			return self.treesum[root]
		left = 2 * root + 1
		right = 2 * root + 2
		mid = (l + r) // 2
		if qr <= mid:
			return self._query(left, l, mid, ql, qr)
		elif mid + 1 <= ql:
			return self._query(right, mid + 1, r, ql, qr)
		else:
      # here
			return min(self._query(left, l, mid, ql, mid), self._query(right, mid + 1, r, mid + 1, qr))

线段树结点实现模板

class SegTreeNode:
    def __init__(self, l: int, r: int):
        self.treesum = 0
        self.l = l
        self.r = r
        self.left = None
        self.right = None
    
    @property
    def _mid(self) -> int:
        return (self.l + self.r) // 2
    
    @property
    def _left(self):
        if self.left == None:
            self.left = SegTreeNode(self.l, self._mid)
        return self.left
    
    @property
    def _right(self):
        if self.right == None:
            self.right = SegTreeNode(self._mid + 1, self.r)
        return self.right

    def update(self, ID: int, diff: int) -> None:
        self.treesum += diff
        if self.l == self.r:
            return 
        if ID <= self._mid:
            self._left.update(ID, diff)
        else:
            self._right.update(ID, diff)
    
    def query(self, ql: int, qr: int) -> int:
        if qr < self.l or self.r < ql:
            return 0
        if ql <= self.l and self.r <= qr:
            return self.treesum
        return self._left.query(ql, qr) + self._right.query(ql, qr) 

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = max(instructions)
        ST = SegTreeNode(0, n)
        res = 0
        for x in instructions:
            lesser = ST.query(1, x - 1) if 1 <= x-1  else 0
            greater = ST.query(x+1, n) if x+1 <= n else 0
            res += min(lesser, greater)
            res %= MOD
            ST.update(x, 1)
        return res

作者：XingHe_XingHe
链接：<https://leetcode.cn/problems/create-sorted-array-through-instructions/solution/cpython3-dan-dian-geng-xin-1shu-zhuang-s-ktcj/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。