位运算中x(-x) Lowbit(x)的理解

跟大佬学习树状数组的学习笔记：

取到的结果就是把自身x最低位1和后面的0保存，前面都不要了
e.g：
lowbit（6）：6的二进制是（110）所以结果就是（10）
lowbit（7）：7的二进制是（111）所以结果就是（1）
然后把结果转化10进制就可以了
快速办法直接看 最低位1取到的是第几位，然后2的几次方就可以了
比如lowbit（6） 最低位1 在第1位上 所以2^1=2;
lowbit (7) 最低位1 在第0位上 所以2^0=1

附上一个特别棒的网站，帮助理解（动画演示代码）：
https://visualgo.net/zh/fenwicktree

附上树状数组代码（方便以后自己学习）：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define For(a,b) for(int a=0;a
#define mem(a,b) memset(a,b,sizeof(a))
#define _mem(a,b) memset(a,0,(b+1)<<2)
#define lowbit(a) ((a)&-(a))
using namespace std;
typedef long long ll;
const int maxn =  5*1e4+5;
const int INF = 0x3f3f3f3f;
int c[maxn];
void update(int x,int y,int n){for(int i=x;i<=n;i+=lowbit(i))c[i] += y;
}
int getsum(int x){int ans = 0;for(int i=x;i;i-=lowbit(i))ans += c[i];return ans;
}
int main()
{int t;int n;int x,y,z;string s;cin >> t ;for(int j=1;j<=t;j++){scanf("%d",&n);_mem(c,n);      //初始化数组中前n+1个数为0for(int i=1;i<=n;i++){scanf("%d",&z);update(i,z,n);}cout <<"Case "<<j<<":"<<endl;while(1){cin >> s;if(s[0] == 'E')break;scanf("%d%d",&x,&y);if(s[0] == 'Q')cout << getsum(y)-getsum(x-1)<<endl;else if(s[0] == 'A')update(x,y,n);elseupdate(x,-y,n);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！