[python刷题模板] 树状数组

• • 一、 算法&数据结构
  • • 1. 描述
    • 2. 复杂度分析
    • 3. 常见应用
    • 4. 常用优化
  • 二、 模板代码
  • • 1. 单点更新，区间求和(PUIQ)
    • 2. 区间更新，单点询值
    • 3.区间更新，区间求和
  • 三、其他

区间问题通常我会用线段树，比较好理解；但树状数组常数实在太低了，有的题估计卡你，学不明白，只好打板

1. 查询query, O(log₂n)
2. 更新update，O(log₂n)

1. 单点更新，区间求和
2. 区间更新，单点求和
3. 区间更新，区间求和

1. lowerbit() *O(1)*解法，需要理解补码知识

例题: 307. 区域和检索 - 数组可修改
树状数组最常用最擅长部分，当然，线段树能做

class BinIndexTree:
    def __init__(self, size):
        self.size = size
        self.bin_tree = [0 for _ in range(size+5)]
    def add(self,i,v):
        while i<=self.size :
            self.bin_tree[i] += v
            i += self.lowbit(i)
    def update(self,i,v):
        val = v - (self.sum(i)-self.sum(i-1))
        self.add(i,val)
    def sum(self,i):
        s = 0
        while i >= 1:
            s += self.bin_tree[i]
            i -= self.lowbit(i)
        return s
    def lowbit(self,x):
        return x&-x

class NumArray:

    def __init__(self, nums: List[int]):
        self.size = len(nums)
        self.nums = nums
        self.tree = BinIndexTree(self.size)
        for i,num in enumerate(nums):
            self.tree.add(i+1,num)
        
    def update(self, index: int, val: int) -> None:         
        add = val - self.nums[index]
        self.nums[index] = val
        self.tree.add(index+1,add)       

    def sumRange(self, left: int, right: int) -> int:        
        return self.tree.sum(right+1) - self.tree.sum(left)         

暂无例题

树状数组经典案例，要用差分数组理解：
这个实际上是用树状数组维护原数组的差分数组c[i]=a[i]-a[i-1]
求原数组的值a[i]实际上是差分数组的前缀sum(c[0]…c[i]),所以get a[i]可以用sum c[i]表示,
而原数组a区间[x,y]更新+v，产生的效果是:x位置比x-1位置大了v,y+1位置比y小了v;
对差分数组c来说,产生变化的就是c[x]增加了v，c[y+1]减小了v,因为c数组代表的是a中每个数比前一个数的差。

	- 结论：

• sum[i]代替get[i],单点求值
• 两步add(l,v)和add(r+1,-v),区间更新

class BinIndexTree:
    def __init__(self, size):
        self.size = size
        self.bin_tree = [0 for _ in range(size+5)]
    def add(self,i,v):
        while i<=self.size :
            self.bin_tree[i] += v
            i += self.lowbit(i)
    def update(self,i,v):
        val = v - (self.sum(i)-self.sum(i-1))
        self.add(i,val)
    def sum(self,i):
        s = 0
        while i >= 1:
            s += self.bin_tree[i]
            i -= self.lowbit(i)
        return s
    def lowbit(self,x):
        return x&-x
   	def _point_query(self,i):
   		return self.sum(i)
   	def _interval_add(self,l,r,v):
   		self.add(l,v)
   		self.add(r+1,-v)

参考链接: 树状数组—区间更新，区间查询
我们假设sigma(r，i)表示r数组的前i项和
观察式子：
a[1]+a[2]+…+a[n]

= (c[1]) + (c[1]+c[2]) + … + (c[1]+c[2]+…+c[n])

= n*c[1] + (n-1)*c[2] +… +c[n]

= n * (c[1]+c[2]+…+c[n]) - (0c[1]+1c[2]+…+(n-1)*c[n]) (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

=n*sigma(c,n) - sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询
这里我先不写python了，遇到题再说吧
题目链接：http://poj.org/problem?id=3468

#include 
#include 
#include 
using namespace std;
typedef long long ll ;
const int maxn = 1e5 + 10;
 
ll a[maxn], c1[maxn], c2[maxn];
int  n , m;
 
int lowbit(int i){
    return i & (-i);
}
 
void Build (ll *ar, int i, ll x){
    while (i <= n){
        ar[i] += x;
        i += lowbit(i);
    }
}
 
ll add (ll *ar, int x){
    ll ans = 0;
    while (x > 0){
        ans += ar[x];
        x -= lowbit(x);
    }
    return ans ;
}
 
int main (){
    while (~scanf("%d%d",&n, &m)){
        a[0] = 0;
        for (int i = 1; i <= n; i++){
            scanf("%lld", &a[i]);
            Build (c1, i, (a[i] - a[i - 1]));
            Build (c2, i, (i - 1) * (a[i] - a[ i - 1]));
        }
        char op[2];
        int x, y ;
        ll z;
        while (m--){
            scanf("%s",op);
            if (op[0] == 'Q'){
                scanf("%d%d",&x,&y);
                ll ans = y * add(c1, y) - add(c2, y) - ((x - 1)*add(c1, x- 1) - add(c2, x - 1));
                printf("%lldn",ans);
            }
            else {
            scanf("%d%d%lld",&x,&y,&z);
            Build (c1, x, z);
            Build (c1, y + 1, -z);
            Build (c2, x, (x - 1) * z);
            Build (c2, y + 1, y * (-z));
            }
        }
    }
    return 0;
}

1. 树状数组还有有很多更巧妙的用法，更多的不会了，参照英雄哥的博文吧。
   https://blog.csdn.net/WhereIsHeroFrom/article/details/113598114