树状数组C++——算法设计与分析,附详细解析-创新互联

文章目录
      • 什么是树状数组
      • lowbit(x)
      • 树状数组的构建
      • 如何求区间和呢
      • 如何更新一个元素呢
      • 二话不说上代码

芮城ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为成都创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!什么是树状数组

树状数组可以快速求出数组任意区间的和,具体来说是在 O ( l o g   N ) O(log\ N) O(log N)的时间内求出一段区间的和,而更新单个元素的值也需要 O ( l o g   N ) O(log\ N) O(log N)时间来维护。首先对树状数组留下一个简单的印象,如下图所示, A A A数组是原数组, C C C数组是树状数组,我们要查询 1 − 6 1-6 1−6区间的和,我们只需要求出 C 6 + C 4 = 21 C6 + C4 = 21 C6+C4=21的值即可,是不是很快速,那如何实现这样的结构呢?
请添加图片描述
对于序列 A A A,我们设置一个数组 C C C与 A A A有同样的大小, C [ i ] C[i] C[i]的求法如下:
C [ i ] = a [ i − 2 k + 1 ] + ⋯ + a [ i ] C[i]=a[i-2^k+1]+\cdots+a[i] C[i]=a[i−2k+1]+⋯+a[i]
其中, k k k表示 i i i 末尾连续 0 0 0 的个数,而 2 k 2^k 2k 就表示 i i i 最右边的第一个 1 1 1 和右边连续的 0 0 0 组成的数,就那拿 12 12 12 打比方, 12 = ( 1100 ) 2 12=(1100)_2 12=(1100)2​,右边连续的零有两个,则 k = 2 k=2 k=2, 2 k = 2 2 = ( 100 ) 2 2^k=2^2=(100)_2 2k=22=(100)2​,就是 i i i 保留最右边的 1 1 1 ,其余位全变成 0 0 0, C C C即为树状数组。

那么给定一个 i i i ,如何来求出 k k k 呢?

lowbit(x)

l o w b i t ( x ) lowbit(x) lowbit(x)表示的就是保留 x x x 最后一个 1 1 1,其余全变为 0 0 0 的数。

我们假设一个二进制数表示为 x x x x 100 ⋯ 00 xxxx100\cdots00 xxxx100⋯00, x x x表示 0 0 0 或者 1 1 1,我们将它减一,得到 x x x x 011 ⋯ 11 xxxx011\cdots11 xxxx011⋯11,注意 x x x x xxxx xxxx表示的数没有变,只有最后一位 1 1 1 和右边变化了,我们将这两个数异或
     x x x x 100 ⋯ 00 ⊕ x x x x 011 ⋯ 11 = 0000   111 ⋯ 11 \ \ \ \ xxxx100\cdots00\\ \oplus xxxx011\cdots11\\ \rule[+3pt]{4.3cm}{0.05em}\\ = 0000\ 111\cdots11     xxxx100⋯00⊕xxxx011⋯11=0000 111⋯11
就得到一个 m a s k mask mask,最右边第一个 1 1 1 的左边全 0 0 0,右边全 1 1 1,我们再将这个数与原来的 i i i 相与,就可以得到 l o w b i t ( x ) lowbit(x) lowbit(x)了。
         0000   111 ⋯ 11 a n d   x x x x 100 ⋯ 00    =   0000   100 ⋯ 00 \ \ \ \ \ \ \ \ 0000\ 111\cdots11\\ and\ xxxx100\cdots00\\ \rule[+3pt]{4.3cm}{0.05em}\\ \ \ =\ 0 0 0 0 \ 100\cdots00         0000 111⋯11and xxxx100⋯00  = 0000 100⋯00
由此,我们可以推出 l o w b i t ( x ) lowbit(x) lowbit(x) 函数的求法:
l o w b i t ( x ) = x & [ x ⊕ ( x − 1 ) ] lowbit(x)=x\&[x\oplus (x-1)] lowbit(x)=x&[x⊕(x−1)]
而 x ⊕ ( x − 1 ) = − x x\oplus(x-1)=-x x⊕(x−1)=−x,化简上式可得:
l o w b i t ( x ) = x & ( − x ) lowbit(x)=x\&(-x) lowbit(x)=x&(−x)
我们可以定义一个宏来求 l o w b i t ( x ) lowbit(x) lowbit(x):

#define lowbit(x) ((x)&(-(x)))

回到 C C C 数组的定义,我们可以将其改写为
C [ i ] = a [ i − l o w b i t ( i ) + 1 ] + ⋯ + a [ i ] C[i]=a[i-lowbit(i)+1]+\cdots+a[i] C[i]=a[i−lowbit(i)+1]+⋯+a[i]
那么,我们可以得出:

在这里插入图片描述

树状数组的构建

树状数组成员变量包含元素个数 n n n 以及树状数组 c [ M A X ] c[MAX] c[MAX],下面的代码展示了构建树状数组的过程,首先求出 s u m sum sum 数组, s u m [ i ] sum[i] sum[i] 表示 1 − i 1-i 1−i 的和,再根据树状数组的定义求出 C C C,构建树状数组的时间复杂度为 O ( N ) O(N) O(N)。

private:
	int n;
	int c[MAX];//树状数组 
public:
    treeArray(int arr[], int num){n = num; 
        int sum[n + 1]; 		//sum[i]表示1-i的和 
        for(int i = 1; i<= n; i++)		sum[i] = sum[i-1] + arr[i-1];
        for(int i = 1; i<= n; i++)		c[i] = sum[i] - sum[i - lowbit(i)];		//按照C的定义,构建树状数组 
    }
如何求区间和呢

我们现在已知了 C [ i ] C[i] C[i],如何求出 s u m ( k ) = A [ 1 ] + A [ 2 ] + ⋯ + A [ k ] sum(k)=A[1]+A[2]+\cdots+A[k] sum(k)=A[1]+A[2]+⋯+A[k]呢,打个比方,现在要求 s u m ( 7 ) sum(7) sum(7),有上述 C C C 的定义,可以看出 s u m ( 7 ) = C 7 + C 6 + C 4 = ( A 7 ) + ( A 5 + A 6 ) + ( A 1 + A 2 + A 3 + A 4 ) sum(7)=C7+C6+C4=(A7)+(A5+A6)+(A1+A2+A3+A4) sum(7)=C7+C6+C4=(A7)+(A5+A6)+(A1+A2+A3+A4),我们通过一定的规律,可以找出来一个通用公式
s u m ( k ) = C [ n 1 ] + C [ n 2 ] + ⋯ + C [ n m ] n m = k , n i − 1 = n i − l o w b i t ( n i ) sum(k)=C[n_1]+C[n_2]+\cdots+C[n_m]\\ n_m=k,\quad n_{i-1}=n_i-lowbit(n_i) sum(k)=C[n1​]+C[n2​]+⋯+C[nm​]nm​=k,ni−1​=ni​−lowbit(ni​)
就拿 7 7 7 打比方, n n n来表示 C C C的下标,初始值为 7 7 7,直到减到 $0 $为止:
n = 7 , s u m ( 7 ) + = C [ 7 ] , n = 7 − l o w b i t ( 7 ) = 6 n = 6 , s u m ( 7 ) + = C [ 6 ] , n = 6 − l o w b i t ( 6 ) = 4 n = 4 , s u m ( 7 ) + = C [ 4 ] , n = 4 − l o w b i t ( 4 ) = 0 n=7,\quad sum(7)+=C[7],\quad n=7-lowbit(7)=6\\ n=6,\quad sum(7)+=C[6],\quad n=6-lowbit(6)=4\\ n=4,\quad sum(7)+=C[4],\quad n=4-lowbit(4)=0 n=7,sum(7)+=C[7],n=7−lowbit(7)=6n=6,sum(7)+=C[6],n=6−lowbit(6)=4n=4,sum(7)+=C[4],n=4−lowbit(4)=0
具体证明如下,感兴趣的可以看一看
请添加图片描述

现在回到 C [ i ] C[i] C[i]含义的理解上, C [ i ] = a [ i − l o w b i t ( i ) + 1 ] + ⋯ + a [ i ] C[i]=a[i-lowbit(i)+1]+\cdots+a[i] C[i]=a[i−lowbit(i)+1]+⋯+a[i],其实 i − l o w b i t ( i ) + 1 i-lowbit(i)+1 i−lowbit(i)+1就是把 i i i 最右边的 1 1 1 去掉,然后再加 1 1 1,从这个下标开始一直加到 i i i,因为 k k k 的二进制最多有 l o g 2 k log_2k log2​k 个 1 1 1 ,所以 s u m ( k ) sum(k) sum(k)最多有 l o g 2 k log_2k log2​k 项,求区间和的时间复杂度就是 l o g 2 k log_2k log2​k。

接下来,如果要求区间 [ a , b ] [a,b] [a,b] 的和,只需要用 s u m ( b ) − s u m ( a − 1 ) sum(b)-sum(a-1) sum(b)−sum(a−1) 即可表示。

下面就是求区间和的两个函数,一个参数的函数表示求 [ 1 − i ] [1-i] [1−i] 的和,两个参数的函数表示求 [ a − b ] [a-b] [a−b] 的和

int getsum(int i){//求A[1-i]的和 
    int res=0;
    while(i >0){res += c[i];
        i -= lowbit(i);
    } 
    return res;
}
int getsum(int a, int b){//求A[a-b]的和
	return getsum(b) - getsum(a-1);
} 
如何更新一个元素呢

假设我要更新 A [ 2 ] A[2] A[2] ,那么树状数组需要更新对应的 C [ 2 ] , C [ 4 ] , C [ 8 ] , C [ 16 ] C[2], C[4],C[8],C[16] C[2],C[4],C[8],C[16] ,我们也可以从中找到规律,如果要更新 A [ i ] A[i] A[i] ,那么下面几项也需要更新:
C [ n 1 ] , C [ n 2 ] , ⋯   , C [ n m ] n 1 = i , n i + 1 = n i + l o w b i t ( n i ) C[n_1],C[n_2],\cdots,C[n_m]\\ n_1=i,\quad n_{i+1}=n_i+lowbit(n_i) C[n1​],C[n2​],⋯,C[nm​]n1​=i,ni+1​=ni​+lowbit(ni​)
同理拿 2 2 2 做为例子,用 n n n 表示树状数组 C C C 的下标,初始值为 2 2 2,直到 n n n 大于数组的大小为止
n = 2 , u p d a t e   C [ 2 ] , n = 2 + l o w b i t ( 2 ) n = 4 , u p d a t e   C [ 4 ] , n = 4 + l o w b i t ( 4 ) n = 8 , u p d a t e   C [ 8 ] , n = 8 + l o w b i t ( 8 ) n = 16 , u p d a t e   C [ 16 ] , n = 16 + l o w b i t ( 16 ) n=2,\quad update\ C[2],\quad n=2+lowbit(2)\\ n=4,\quad update\ C[4],\quad n=4+lowbit(4)\\ n=8,\quad update\ C[8],\quad n=8+lowbit(8)\\ n=16,\quad update\ C[16],\quad n=16+lowbit(16)\\ n=2,update C[2],n=2+lowbit(2)n=4,update C[4],n=4+lowbit(4)n=8,update C[8],n=8+lowbit(8)n=16,update C[16],n=16+lowbit(16)
最后 n n n 大于 16 16 16 ,更新结束,同理,更新一个元素总的时间也是 O ( l o g N ) O(log N) O(logN),但是如果想要更新一个区间的元素就要 O ( N l o g N ) O(NlogN) O(NlogN) 的时间复杂度了,可以考虑另一种结构——线段树会更好,这里不具体介绍。

下面是在位置 i i i 上加 k k k 的代码

void add(int i, int k){//在位置i上加k 
    while(i<= n){c[i] += k;
        i += lowbit(i);
    } 
}
二话不说上代码

这样以来,我们就学会了树状数组啦,代码是不是很精简,但是功能却很强大哇。

#includeusing namespace std;
#define lowbit(x) ((x)&(-(x)))
#define MAX 10005
class treeArray{private:
	int n;
	int c[MAX];//树状数组 
public:
	treeArray(){};
	treeArray(int arr[], int num){n = num; 
		int sum[n + 1]; 		//sum[i]表示1-i的和 
		for(int i = 1; i<= n; i++)		sum[i] = sum[i-1] + arr[i-1];
		for(int i = 1; i<= n; i++)		c[i] = sum[i] - sum[i - lowbit(i)];		//按照C的定义,构建树状数组 
	}
	void add(int i, int k){//在位置i上加k 
		while(i<= n){	c[i] += k;
			i += lowbit(i);
		} 
	}
	int getsum(int i){//求A[1-i]的和 
		int res=0;
		while(i >0){	res += c[i];
			i -= lowbit(i);
		} 
		return res;
	}
	int getsum(int a, int b){//求A[a-b]的和
		return getsum(b) - getsum(a-1);
	}  
	void show(){for(int i = 1; i<= n; i++) cout<< c[i]<< ' ';cout<< endl;}
};
int main(void){int n = 10;
	int a[n] = {1,2,3,4,5,6,7,8,9,10};	//定义数组一开始的值 
	treeArray arr(a, n);
	cout<< "4到10的和为:"<< arr.getsum(4,10)<< endl;		//求数组4-10的和 
	cout<< "1到4的和为:"<< arr.getsum(4)<< endl; 			//求数组1-4的和 
	cout<< "将4的值加5"<< endl; 
	arr.add(4,5);						//将4的值加5 
	cout<< "1到4的和变为:"<< arr.getsum(4,10)<< endl;
	arr.show();
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站名称:树状数组C++——算法设计与分析,附详细解析-创新互联
网页链接:http://scyanting.com/article/dohjgd.html