首页 > 代码库 > 区间处理之分块
区间处理之分块
分块这种思路很常见，就是把一个数列划分成k块，然后在块的基础上进行操作。
假如每块的大小为magic，那么长度为n的数列则一共会划分成ceil(n/magic)块。这样会有一些性质：
1.原数列第i个的块号为i/magic，是块内的第i%magic个（不过这一条没有用）。
2.假如i%magic==0，说明i是第i/magic块的起点，第i/magic块的范围是[i/magic, (i+1)/magic)。
下面是用分块思想对一个长为n的数列的操作：查找子区间的最大值和修改某个点的值。
1 const int maxn = 50500; 2 const int magic = 10; 3 int n, q; 4 int h[maxn], b[maxn]; 5 6 void init() { 7 for(int i = 0; i < n; i++) { 8 if(i % magic == 0 || h[i] > b[i/magic]) { 9 b[i/magic] = h[i];10 }11 }12 }13 14 int query(int l, int r) {15 int ret = h[l];16 for(int i = l; i <= r; ) {17 if(i % magic == 0 && i + magic - 1 <= r) {18 ret = max(ret, b[i/magic]);19 i += magic;20 }21 else {22 ret = max(ret, h[i++]);23 }24 }25 return ret;26 }27 28 void update(int x, int v) {29 h[x] = v;30 int l = x / magic * magic;31 int r = l + magic;32 for(int i = l; i < r; i++) {33 if(i % magic == 0 || h[i] > b[i/magic]) {34 b[i/magic] = h[i];35 }36 }37 }
区间处理之分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。