树状数组知识点

发布时间：2020-12-14 04:17:21 所属栏目：大数据来源：网络整理

导读：1.单点加入 void add(int p,int x){for(int i=p;i=n;i+=lowbit(i)){t[i]+=x;}} 注意从编号开始，是每次+=lowbit(i)操作。另外，t[i]是+=而不是=。? ? 2.区间查询 int query(int p){int re=0;for(int i=p;i0;i-=lowbit(i)){re+=t[i];}return re;} 注意从p~1,

1.单点加入

void add(int p,int x){
	for(int i=p;i<=n;i+=lowbit(i)){
		t[i]+=x;
	}
}

　注意从编号开始，是每次+=lowbit(i)操作。另外，t[i]是+=而不是=。?

2.区间查询

int query(int p){
	int re=0;
	for(int i=p;i>0;i-=lowbit(i)){
		re+=t[i];
	}
	return re;
}

　　注意从p~1,是每次-=lowbit(i)。

3.初始化

for(int i=1;i<=n;i++){
		for(int j=i-lowbit(i)+1;j<=i;j++){
			t[i]+=a[j];
		}
	}

　　注意从i-lowbit(i)+1开始，j<=i；t[i]是+=。（i枚举每一个未处理的线性元素）

4.别忘了lowbit

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

　　这里使用内联函数（inline）会更好。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!