# 前言

笔者花了一个月的时间学习了线段树,但是那玩意儿代码太长(其实是我懒)常数又大,就打算探究一种新的算法。于是我就学习了树状数组。

# 引入概念

树状数组和线段树类似,都是处理区间上问题的,但又略有不同。树状数组的性质:

  1. 一个节点,编号是xx,则它的父亲节点编号是x+lowbit(x)x+lowbit(x),且最顶层节点的编号就是数组的长度;
  1. 一个节点,编号是xx,则它的管辖范围是(xlowbit(x),x]\left( x-lowbit(x),x \right]

# lowbitlowbit函数

# 概念

lowbit(x)lowbit(x)表示x二进制下最低位的11的数码。比如:

lowbit(5)=lowbit((0101)2)=(1)2=1lowbit(5)=lowbit((0101)_2)=(1)_2=1lowbit(24)=lowbit((00011000)2)=(1000)2=8lowbit(24)=lowbit((00011000)_2)=(1000)_2=8

# 实现

知道了lowbitlowbit的概念,我们该怎么去求呢?

假设要求的数是2424,我们先把它转换成二进制数0001100000011000,然后对这个二进制数取补码,结果是二进制数1110111011101110,然后一下可得到二进制数10001000,也就是最后结果。为什么呢?

我们可以把取补码的步骤拆开来。先取反码,得到1110011111100111,然后加11,得到1110111011101110,发现刚好把最低位的00右边的所有11向左移了一位,覆盖掉了这个00,而这个00的位置在原码上是11,与一下自然就是11,最后结果自然就是lowbitlowbit了。

由于取补码相当于取负,那么lowbit(x)lowbit(x)就等于x&(x)x\&(-x),代码显而易见:

int lowbit(int x){
	return x&(-x);
}

# 树状数组实现

# 单点加减+区间求和

# 建树

树状数组不用建树,只要把需要加入树状数组的数依次加进去就好了。

# 单点加减-修改第xx个元素

其实单点修改很简单,只要将树状数组中的第xx个元素修改,再向上维护即可。

代码:

void add(int index,int n,int tot){	//tot表示总共有tot个元素。
    int i=index;
    while(i<=tot){
        tree[i]+=n;	//维护树状数组
        i+=lowbit(i);
    }
}

# 区间求和-查询[l,r]\left[ l,r \right]区间内所有数的和

我们设定一个查询函数,每次调用查询函数传入一个xx,查询11~xx区间内所有数的和。这个函数代码如下:

int query(int x){
    int i=x,ans=0;
    while(i){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}

query(r)query(l1)query(r)-query(l-1)就是最终结果。

# 推荐题目

#include<cstdio>
using namespace std;
int lowbit(int x){
    return x&(-x);
}

int tree[20000001],n,m;

void add(int index,int n,int tot){	//单点修改
    int i=index;
    while(i<=tot){
        tree[i]+=n;
        i+=lowbit(i);
    }
}

int query(int x){	//区间查询
    int i=x,ans=0;
    while(i){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){	//初始化
        int x;
        scanf("%d",&x);
        add(i,x,n);
    }
    for(int i=0;i<m;i++){
        int m,x,y;
        scanf("%d%d%d",&m,&x,&y);
        if(m==1)add(x,y,n);
        else printf("%d\n",query(y)-query(x-1));
    }
    return 0;
}

:::


Updated on Jun. 9th, 2019

# 区间加减+单点查询

# 差分

在这个问题里,我们不再记录每个数具体的值,而是记录这个数与它前一个数的差。这会非常有效地解决区间加减的问题。

# 建树

照样不需要建树。但是,这与前面的初始化方法又略有不同:

int pre=0;
for(int i=1;i<=n;i++){	//初始化
    int x;
    scanf("%d",&x);
    add(i,x-pre,n);
    pre=x;	//记录前一个数
}

# 区间加-将[l,r]\left[ l,r \right]区间内所有数加上nn

我们只要把差分数组中第ll个元素加上nn,再将第r+1r+1个元素减去nn即可。

代码:

int modifyAdd(int l,int r,int n,int tot){
    add(l,n,tot);
    add(r+1,-n,tot);	//一个数减去另一个数等于加上那个数的相反数
}

# 单点查询-查询第xx个元素的值

我们如何从差分数组中还原第xx数呢?其实很简单,只要将差分数组中前xx个数加起来就行了。代码和上面的queryquery函数一样。

# 推荐题目

#include<iostream>
using namespace std;

int lowbit(int x){
    return x&(-x);
}

int tree[1000001];

int add(int index,int n,int tot){
    int i=index;
    while(i<=tot){
        tree[i]+=n;
        i+=lowbit(i);
    }
}

int modifyAdd(int l,int r,int n,int tot){	//区间加
    add(l,n,tot);
    add(r+1,-n,tot);
}

int query(int index){
    int i=index,ans=0;
    while(i){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}

int main(){
    int n,m,pre=0;
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){	//初始化
        int x;
		scanf("%d",&x);
        add(i,x-pre,n);
        pre=x;
    }
    while(m--){
        int m,x,y,z;
		scanf("%d%d",&m,&x);
        if(m==1){scanf("%d%d",&y,&z);modifyAdd(x,y,z,n);}
        else printf("%d\n",query(x));
    }
    return 0;
}
2019 06 08 Sat 08:00:00
2020 10 17 Sat 07:42:15