笔记-区间问题

听课笔记

2018/11/24

给定一个数列，可能会有多种操作

数据规模(n=10^5)

(Q=10^5),

扫描一遍(O(nQ)),(10^8)以上1000ms可能做不了

解决方案

1.树状数组

用来处理区间和

	int c[i];
    int lowbit(int);

2.线段树

原理：区间的可加性

修改，查询，延时标记

本子节点的值:

	t[p].val=f(t[p<<1].val,t[p<<1|1].val);

3.分块

e.g. BZOJ2724
时间复杂度：(O(Nsqrt{N}))

将数列分成(sqrt{N})块

记录：

1.sum[i];
2.add[i];
3.left side:(i-1)*sqrt(N)+1;
  right side:i*sqrt(N);
4.pos[j]=i; a[j] is the i-th blocks