社区讨论

关于树状数组

2026/03/05 21:35学术版参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

我在写树套树时写的是树状数组套线段树，然后我的树状数组是这么写的：

CPP

void ad(int x,int v){for(int i=x;i<=n;i+=(i&-x/*不是 i!!!*/))up(rt[i],1,sz,a[x],v);}

但这是能过的。

然后我去【模版】树状数组 1 里面把 up 函数改成了这样：

CPP

void up(int x,int v){int a=x;while(x<=n)t[x]+=v,x+=(x&-a);}

然后这个也能过。

求证伪这个做法，或者证明这个做法是真的（正确性和时间复杂度）。

共 6 条回复，欢迎继续交流。

正在加载回复...