树状数组学习笔记

简介

树状数组是一个可以在 \(O(\log n)\) 的时间复杂度内支持单点修改和查询前缀和的操作的数据结构。

\(\text{lowbit}\)

\(\text{lowbit}\) 是指一个数在二进制下最末尾的1的位置。\(\text{lowbit(x) = x and -x}\)

写法

建立

把编号为 \(i\) 的点和编号为\(i+\text{lowbit}(i)\)的点连起来。

然后把点\(i\)到根节点路径上的所有点的\(val\)加上\(a_i\)。

修改

把点\(i\)到根节点路径上的所有点的\(val\)加上\(data\)。

查询

如果要查询\([l,r]\)的和，就可以用\(r\)的前缀和减去\(l-1\)的前缀和。

如何求前缀和呢？

就是从点 \(i\) 一直往下跳 (\(\text{-lowbit(i)}\))，直到跳到0，把中间的所有\(val\)加起来就是前缀和了。

代码

int val[MAXN];
void change(int x,int data){//修改&建立
    for(int i=x;i<=MAXN;i+=lowbit(i))val[i]+=data;
}
int ask(int x){//前缀和
    int ans=0;
    for(int i=x;i!=0;i-=lowbit(i))ans+=val[i];
    return ans;
}
int ask(int l,int r){//查询
    return ask(r)-ask(l-1);
}

二维树状数组

可以求出二维数组里的前缀和，时间复杂度\(O(\log^2 n)\)。

与一维树状数组相似。

int val[MAXN][MAXN];
void change(int x,int y,int data){//修改&建立
    for(int i=x;i<=MAXN;i+=lowbit(i))
    for(int j=y;j<=MAXN;j+=lowbit(j))
    val[i][j]+=data;
}
int ask(int x,int y){//前缀和
    int ans=0;
    for(int i=x;i!=0;i-=lowbit(i))
    for(int j=y;j!=0;j-=lowbit(j))    
    ans+=val[i][j];
    return ans;
}
int ask(int x1,int y1,int x2,int y2){//查询
    return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
}