Binary Indexed Tree

Binary Indexed Tree

给定一个数组 arr
有修改查询两种操作

  1. add(idx,val)

arr[idx]+=val

  1. query(left,right)

return sum(arr[left],arr[left+1],...,arr[right])

Overview

初始化复杂度 O(n)
修改复杂度 O(logN)
查询复杂度 O(logN)

对比数组,前缀和数组,线段树均有优势

Lowbit

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

Add

def add(index, value):
    while index <= size:
        tree[index] += value
        index += lowbit(index)

Query

def query(left, right):
    print(presum(right) - presum(left - 1))

def presum(index):
    res = 0
    while (index > 0):
        res += tree[index]
        index -= lowbit(index)
    return res

Build

def build(arr):
    pre = [0 for _ in range(size + 1)]
    for index in range(1, size + 1):
        pre[index] = pre[index - 1] + arr[index - 1]
        tree[index] = pre[index] - pre[index - lowbit(index)]

此方法可以实现O(n)的初始化
对比 先全赋0再一位一位add O(nlogn)有明显优势

Solution

  1. 单点更新、单点查询

    传统数组即可
    
  2. 区间查询 、无更新
    前缀和即可
  3. 单点更新、区间查询
    上文已解决
  4. 区间更新、单点查询
    引入差分, 使得区间更新只要修改两个点

A[i] = ΣD[j]
D[j] = A[j] - A[j-1]

  1. 区间更新、单点查询

    类似4
    并多维护一个树状数组
    `sum1[i] = ΣD[i]`
    `sum2[i] = ΣD[i]*(i-1)`
    
  2. 逆序对(思考)
    举例:

[1,5,2,4,3]有3个逆序对

  1. 二分模型(思考)
    举例:

给定N个编号为1-N的球,将它们乱序丢入一个“神奇的容器”中,作者会在丢的同时询问其中编号第K大的那个球,“神奇的容器”都能够从容作答,并且将那个球给吐出来,然后下次又可以继续往里丟。
1)put x 向容器中放入一个编号为x的球;
2)query K 询问容器中第K大的那个球,并且将那个球从容器中去除

Exercise

http://acm.hdu.edu.cn/showproblem.php?pid=1166

http://acm.hdu.edu.cn/showproblem.php?pid=1541

★★http://poj.org/problem?id=2892

★★http://poj.org/problem?id=3321

★★★http://poj.org/problem?id=1195

★★★http://acm.hdu.edu.cn/showproblem.php?pid=1394

★★★★http://acm.hdu.edu.cn/showproblem.php?pid=5497

★★★★http://acm.hdu.edu.cn/showproblem.php?pid=3303

Add New Comment