树状数组

基本操作

1.（单点修改+区间查询）（可与差分数组结合）（$O(log_2n)$）

def lowbit(x):#返回x的最后一位1
    return x&-x

def add(x,d):#给第x个数加上d
    while x<=n:
        tree[x]+=d
        x+=lowbit(x)

def suma(x):#查询前x个数的和
    res=0
    while x>0:
        res+=tree[x]
        x-=lowbit(x)
    return res

2. （区间修改+区间查询） （$O(log_2n)$）
$\sum_1^ka_i=a_1+a_2+…+a_k$
$=D_1+(D_1+D_2)+(D_1+D_2+D_3)+… +(D_1+D_2+…+D_k)$
$=kD_1+(k-1)D_2+(k-2)D_3+…+(k-(k-1))D_k$
$=k(D_1+D_2+…+D_k)−(D_2+2D_3+…+(k−1)D_k)$
$=k\sum_{i=1}^kD_i-\sum_{i=1}^k(i-1)D_i$

def lowbit(x):
    return x&-x

def add(tree,x,d):
    while x<=n:
        tree[x]+=d
        x+=lowbit(x)

def suma(tree,x):
    res=0
    while x>0:
        res+=tree[x]
        x-=lowbit(x)
    return res
tree1=[0]*N#维护Di
tree2=[0]*N#维护(i-1)Di
#区间修改
add(tree1,x,k)
add(tree1,y+1,-k)
add(tree2,x,(x-1)*k)
add(tree2,y+1,y*(-k))
#区间查询
print((y*suma(tree1,y)-(x-1)*suma(tree1,x-1))-(suma(tree2,y)-suma(tree2,x-1)))

线段树

class Node():
    def __init__(self,l=0,r=0,val=0,add=0):
        self.l=l
        self.r=r
        self.val=val
        self.add=add

MAXN=100010
a=[0]*MAXN
tr=[Node(0,0) for i in range(MAXN<<2)]

def Merge(l,r):
    u=Node()
    u.val=l.val+r.val
    return u

def merge(u,l,r):
    tr[u].val=tr[l].val+tr[r].val

def init_data(u,val):
    tr[u].val=val

def init_tag(u):
    tr[u].add=0

def build(u,l,r):
    tr[u]=Node(l,r)
    init_tag(u);
    if l==r:
        init_data(u,a[l])
        return
    mid=l+r>>1
    build(u<<1,l,mid);build(u<<1|1,mid+1,r)
    merge(u,u<<1,u<<1|1)

def modify_point(u,x,y):
    if tr[u].l==x and tr[u].r==x:
        tr[u].val+=y
        return
    mid=tr[u].l+tr[u].r>>1
    if x<=mid:
        modify_point(u<<1,x,y)
    else:
        modify_point(u<<1|1,x,y)
    merge(u,u<<1,u<<1|1)

def addtag(u,x):
    tr[u].add+=x
    tr[u].val+=x*(tr[u].r-tr[u].l+1)

def push(u):
    if tr[u].add:
        addtag(u<<1,tr[u].add)
        addtag(u<<1|1,tr[u].add)
        init_tag(u)

def query(u,l,r):
    if l<=tr[u].l and tr[u].r<=r:
        return tr[u]
    push(u)#work if modify_range
    mid=tr[u].l+tr[u].r>>1
    if r<=mid:
        return query(u<<1,l,r)
    if l>mid:
        return query(u<<1|1,l,r)
    left=query(u<<1,l,r)
    right=query(u<<1|1,l,r)
    res=Merge(left,right)
    return res

def modify_range(u,l,r,x):
    if l<=tr[u].l and tr[u].r<=r:
        addtag(u,x)
        return
    push(u)
    mid=tr[u].l+tr[u].r>>1
    if r<=mid:
        modify_point(u<<1,l,r,x)
    if l>mid:
        modify_point(u<<1|1,l,r,x)
    merge(u,u<<1,u<<1|1)