树状数组

维护序列前缀和

复杂度 O（logN）

小心不要用到下标[0]

C = [0] * (n + 1)
def lowbit(x):
    return x & (-x)

def add(x, i):
    while x <= n:
        C[x] += i
        x += lowbit(x)
def query(x):
    ans = 0
    while x:
        ans += C[x]
        x -= lowbit(x)
    return ans

线段树

维护区间和

class Node():
    l = 0
    r = 0
    su = 0 #sum
    def __init__(self, l = 0, r = 0, su = 0):
        self.l = l
        self.r = r
        self.su = su

def pushup(u):
    global t
    t[u].su = t[u << 1].su + t[u << 1 | 1].su
def build(u, l, r):
    global t
    if l == r:
        t[u] = Node(l, r, num[r - 1])
        return
    else:
        t[u] = Node(l, r)
        mid = l + r >> 1
        build(u << 1, l, mid)
        build(u << 1 | 1, mid + 1, r)
        pushup(u)
def query(u, l, r):
    if t[u].l >= l and t[u].r <= r: return t[u].su
    mid = t[u].l + t[u]. r >> 1
    ans = 0
    if l <= mid: ans = query(u << 1, l, r)
    if r > mid: ans += query(u << 1 | 1, l, r)
    return ans
def modify(u, x, v):
    if t[u].l == t[u].r: 
        t[u].su +=v
        return
    mid = t[u].l + t[u].r >> 1
    if x <= mid: modify(u << 1, x, v)
    else: modify(u << 1 | 1, x, v)
    pushup(u)

KMP

next数组表示模版串中以i结尾的后缀子串和前缀最大匹配长度

def KMP():
    global s, p
    s = ' ' + s
    p = ' ' + p
    ne = [0] * (n + 2)
    #求next
    j = 0
    for i in range(2, n + 1):
        while j and p[i] != p[j + 1]: j = ne[j]
        if p[i] == p[j + 1]: j += 1
        ne[i] = j
    #匹配
    j = 0
    for i in range(1, m + 1):
        while j and  s[i] != p[j + 1]: j = ne[j]
        if s[i] == p[j + 1]: j += 1
        if j == n:
            print(i - n, end = ' ')
            j = ne[j]