数据结构模板

树状数组

局限性

树状数组被理解成是“可以修改”的前缀和。使用时的局限性：

1. 因为树状数组的本质是前缀和，所以依赖“前缀可减性”
2. 树状数组的单点修改具有局限性，例如“带修改的前缀max,min”问题中，修改必须具有单调性。

1.lowbit

def lowbit(x) -> int:
    return x&-x

2.查询

su = [0] * 100005
def query(pos) -> int:
    res = 0
    while pos:
        res += su[pos]
        pos -= lowbit(pos)
    return res

3.修改

su = [0] * 100005
def change(pos, x) -> None:
    while pos <= n:
        su[pos] += x
        pos += lowbit(pos)

线段树

以维护区间最小值为例

import sys
input = sys.stdin.readline
# py可能会超时
class tnode:
    def __init__(self):
        self.min = 0
        self.lazy = 0
        self.l = 0
        self.r = 0

class SegmentTree:
    def __init__(self, n:int) -> None:
        self.t = [tnode() for _ in range(4 * (n+1))]

    def pushdown(self, root:int) -> None:
        """懒标记下传合并, 根据题目要求设计"""
        if self.t[root].lazy != 0:
            self.t[root].min += self.t[root].lazy
            if self.t[root].l != self.t[root].r:
                ch = root << 1
                self.t[ch].lazy += self.t[root].lazy
                self.t[ch+1].lazy += self.t[root].lazy
            self.t[root].lazy = 0

    def update(self, root:int) -> None:
        """ 区间合并，根据维护的数据变动"""
        ch = root << 1
        self.pushdown(ch)
        self.pushdown(ch+1)
        self.t[root].min = min(self.t[ch].min, self.t[ch+1].min)

    def build(self, root:int, l:int, r:int, ls:list) -> None:
        """递归建树"""
        self.t[root].l = l
        self.t[root].r = r
        self.t[root].lazy = 0
        if l != r:
            mid = (l+r)>>1  # 注C++这么写可能会爆 int，建议参考oi-wiki
            ch = root<<1
            self.build(ch, l, mid, ls)
            self.build(ch+1, mid+1, r, ls)
            self.update(root)
        else:
            self.t[root].min = ls[l]
            # self.mp[l] = root

    def change(self, root:int, l:int, r:int, delta:int) -> None:
        """ 作用: 区间修改 """
        self.pushdown(root)
        if l == self.t[root].l and r == self.t[root].r:
            self.t[root].lazy += delta
            return
        mid = (self.t[root].l+self.t[root].r)>>1
        ch = root<<1
        if r <= mid: self.change(ch,l,r,delta)
        elif l > mid: self.change(ch+1,l,r,delta)
        else:
            self.change(ch,l,mid,delta)
            self.change(ch+1,mid+1,r,delta)
        self.update(root)

    def query_min(self, root:int, l:int, r:int) -> int:
        self.pushdown(root)
        if self.t[root].l == l and self.t[root].r == r:
            return self.t[root].min
        mid = (self.t[root].l+self.t[root].r) >> 1
        ch = root<<1
        if r <= mid: return self.query_min(ch,l,r)
        elif l > mid: return self.query_min(ch+1,l,r)
        else: return min(self.query_min(ch,l,mid),self.query_min(ch+1,mid+1,r))