树状数组笔记
鸣谢：QYQYQYQYQYQ。
______________________________________分割线___________________________________________
更优秀的树状数组模板
struct szsz{ int tree[maxn]; void add(int pos,int num) {for(int i=pos;i<=n;i+=i&-i) tree[i]+=num;} int query(int pos) { int res=0; for(int i=pos;i;i-=i&-i) res+=tree[i]; return res; } };
以及“把树状数组的操作封装在结构体里”的用法[可以看洛谷板子丫]
int main(){
a.add(pos,num);
int ans=a.query(pos);
return 0;
}
______________________________________分割线___________________________________________
1.树状数组可以更快地进行查询、取和、更新等操作——它的“树”的身份（暂时）并没有体现出更大的用途。
2.P2345奶牛集会[复制自聊天记录]
我刚刚从题解里面发现了一个神奇的小技巧 就是可以用分类讨论来处理看似复杂的分段函数 然后接下来的任务只是推出这个函数的式子（这个式子甚至可以是树状数组的模板）
3.P2717寒假作业[储备知识：树状数组求逆序对]
°既严谨又美丽的推理过程呐！
°注意建树的逻辑[所谓深刻的好题]
°怎么判断用特殊方法而不是用暴力树状数组求和：
算一算时间复杂度，两个结论如下。
2^n，大约n<=20;
n方，大约n<=8000
°关于我是怎么算的：2^100000=（2^10)^10000 约等于 （10^3)^(10^4)=10^7
°以及现实是：(10^3)*(10^4)=10^7
°lower_bound的使用：