关于树状数组的玄学优化
  • 板块学术版
  • 楼主2020kanade
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/3/28 20:38
  • 上次更新2023/10/28 05:17:47
查看原帖
关于树状数组的玄学优化
456724
2020kanade楼主2022/3/28 20:38

楼主写某道题的时候为了防止树状数组遇到下标为0而死循环,改了一下add(楼主这里叫cha)和sum的实现,具体修改如下:

before(cha的判0是后来加的):

inline LL lbt(LL x) {return x&(-x);}
inline void cha(LL x,LL q) {while(x<=k&&x) C[x]+=q,x+=lbt(x);}
inline LL sum(LL x) {LL ans=0;while(x>0) ans+=C[x],x-=lbt(x);return ans;}
inline LL getsm(LL l,LL r) {return sum(r)-sum(l-1);}

after:

inline LL lbt(LL x) {return x&(-x);}
inline void cha(LL x,LL q) {for(LL xx=x;xx<=n&&xx>0;xx+=lbt(xx)) C[xx]+=q;}
inline LL sum(LL x) {LL ans=0;for(LL xx=x;xx>0;xx-=lbt(xx)) ans+=C[xx];return ans;}
inline LL getsm(LL l,LL r) {return sum(r)-sum(l-1);}

然后发现好像比之前要快一丢丢?

P3527,改前 改后

但是下面还有两份刚刚测的:

P1972,改前 改后

此时改前又比改后快了......

楼主很好奇是怎么回事,考虑到两道题有个fread的差异,就把fread给去了,之后......

P1972,改前,不带fread 改后,不带fread

速度又一样了?

楼主这个蒟蒻很懵,不知道是测评机波动还是真的有玄学常数优化......如果真的是后者的话请问到底是哪一种有优化,可以的话请尽量讲解一下原理,谢谢......

2022/3/28 20:38
加载中...