浅谈树状数组（为什么lowbit（x）=x&（-x）

树状数组是一种支持单点修改和查询前缀和的数据结构 网上很多讲解它的博客了 这里重点讲一下为什么lowbit(x)=x&(-x)

树状数组代码量相对于线段树基本可以不计(太好写了) 因此NOIp基本不考（？）

但是作为最好写的树状结构 值得好好理解

关于为什么LOWBIT( X ) = X &( -X )

lowbit 要的是你从末尾开始第1个 1 所代表的值

example：13=1101（8+4+1）所以LOWBIT（13）= 1；

那么暴力写一个lowbit就是

复制代码#include<bits/stdc++.h> using namespace std; long long lowbit(long long x){ int ans=1; while (1){ if( x & 1 ) return ans; else { x=x>>1; ans=ans<<1; } } } int main() { long long n; cin>>n; cout<<lowbit (n); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
long long lowbit(long long x){
	int ans=1;
	while (1){
		if( x & 1 ) return ans;
		else {
			x=x>>1;
			ans=ans<<1; 
		}
	}
}
int main()
{
	long long n;
	cin>>n;
	cout<<lowbit (n);
	return 0;
}

　　如果有什么运算符不懂就去百度吧~~~讲的很清楚

但是实际上我们有更好的做法。

要理解为甚LOWBIT（X）＝Ｘ＆－X　要先去百度　反码　和　补码　（超链接都帮你做好了不点一下吗）

欢迎回来 现在我们来聊原理

x变成负数时 他末尾的0全变成1 然后加1又全都变成0

还是举个例子13=1101 反码变成0010 加1变成0011

按位与一下 只有末尾和他都是1 于是lowbit(13)=1

16=10000 反码变成01111 加1变成10000 

按位与时变成10000即16

负数完美的帮你进行了一个反位加1的操作

帮你把原来末尾上一连串的零变成1

再变成0

在最后一堆零的前一位留了一个1 而你要做的就是找见那个1在哪 

如果这个位原来是1 反位加1让他不变 那么肯定这个位原来以前全是0000 

所以就出来了 非常巧妙

每一个数组的区间范围为【x-lowbit[x]】~【x】

剩下的翻翻其他人博客就对上啦 祝你好运

TAG:SIN_XIII ⑨