ST表
区间最大值有一个很重要的性质，允许对于区间重复的操作，即 \(max(a,b,c)=max(max(a,b),max(b,c))\) 这是能用倍增非常关键的一点。例如，求区间和很显然不满足 \(a+b+c=(a+b)+(b+c)\) 也就不能用倍增的思想
设 \(st[i][j]\) 表示从 \(a_{i}\) 开始，向后 \(2^j\) 个元素中最大的元素。根据定义可得 \(st[i][0]=a[i]\)，对于区间长度大于 \(1\) 的情况，发现可以每次从中间拆分成两个区间，递推着求，也就是： $$st[i][j]=max(st[i][j-1],\ st[i+(1\text{<<}(j-1))][j-1])$$考虑如何查询，由于对于区间可以重复操作，只需要把 \([l.r]\) 拆分成 \([l,l+2^k],\ [r-2^k+1,r]\) 两部分，其中 \(k=\log_{2}{(r-l+1)}\)，即 \(max(st[l][k],\ st[r-(1\text{<<}k)+1][k])\)
void init(){lg2[1] = 0;for (int i = 2; i <= maxn - 1; ++i){lg2[i] = lg2[i / 2] + 1;}for (int i = 1; i <= n; ++i){st[i][0] = a[i];}
}
void build(){for (int len = 1; len <= lg2[n]; ++len){int k = (1 << len);for (int i = 1; i <= n - k + 1; ++i){st[i][len] = max(st[i][len - 1], st[i + (1 << (len - 1))][len - 1]);}}
}
int query(int l, int r){int k = lg2[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}
分块
根号分治的思想，把长度为 \(n\) 的数组分成 \(\sqrt{n}\) 块，块长为 \(\sqrt{ n }\)。对于区间的查询，整块的部分用整块的信息，零碎的部分直接暴力求
最基本的单点修改和区间求和；单点修改直接修改，区间求和考虑三部分:
![[分块.png|300]]
左边和右边暴力求和，中间用整块的和即可，这样可以达到查询 \(\operatorname{O}(\sqrt{ n })\) 的时间复杂度
void build(){ blocksize = sqrt(n); blockcnt = n / blocksize; if (n % blocksize) blockcnt++; for (int i = 1; i <= n; ++i){ belong[i] = (i - 1) / blocksize + 1; } for (int i = 1; i <= blockcnt; ++i){ blockl[i] = blocksize * (i - 1) + 1; blockr[i] = min(blocksize * i, n); } for (int i = 1; i <= blockcnt; ++i){ for (int j = blockl[i]; j <= blockr[i]; ++j){ sum[i] += a[j]; } }
}
void update(int x, int k){ a[x] += k; sum[belong[x]] += k;
}
int query(int l, int r){ int ans = 0; if (belong[l] == belong[r]){ for (int i = l; i <= r; ++i){ ans += a[i]; } } else{ for (int i = l; i <= blockr[belong[l]]; ++i){ ans += a[i]; } for (int i = blockl[belong[r]]; i <= r; ++i){ ans += a[i]; } for (int i = belong[l] + 1; i <= belong[r] - 1; ++i){ ans += sum[i]; } } return ans;
}
考虑如何区间修改；对于零散的部分仍然暴力修改，对于中间整块的部分，可以打上一个标记，意为这部分整体都要加上一个 \(tag\)
void build(){ blocksize = sqrt(n); blockcnt = n / blocksize; if (n % blocksize) blockcnt++; for (int i = 1; i <= n; ++i){ belong[i] = (i - 1) / blocksize + 1; } for (int i = 1; i <= blockcnt; ++i){ blockl[i] = blocksize * (i - 1) + 1; blockr[i] = min(n, blocksize * i); } for (int i = 1; i <= blockcnt; ++i){ for (int j = blockl[i]; j <= blockr[i]; ++j){ sum[i] += a[j]; } }
}
void update(int l, int r, int k){ if (belong[l] == belong[r]){ for (int i = l; i <= r; ++i){ a[i] += k; sum[belong[l]] += k; } } else{ for (int i = l; i <= blockr[belong[l]]; ++i){ a[i] += k; sum[belong[l]] += k; } for (int i = blockl[belong[r]]; i <= r; ++i){ a[i] += k; sum[belong[r]] += k; } for (int i = belong[l] + 1; i <= belong[r] - 1; ++i){ tag[i] += k; } }
}
int query(int l, int r){ int ans = 0; if (belong[l] == belong[r]){ for (int i = l; i <= r; ++i){ ans += a[i] + tag[belong[i]]; } } else{ for (int i = l; i <= blockr[belong[l]]; ++i){ ans += a[i] + tag[belong[i]]; } for (int i = blockl[belong[r]]; i <= r; ++i){ ans += a[i] + tag[belong[i]]; } for (int i = belong[l] + 1; i <= belong[r] - 1; ++i){ ans += sum[i] + tag[i] * (blockr[belong[i]] - blockl[belong[i]] + 1); } } return ans;
}