线段树入门
【Java并发工具类】CountDownLatch和CyclicBarrier
线段树入门
引题
有一个包括(N)个数的序列((N leq 1e6)),给(Q(le 1e6))个操纵,每一个操纵是下面两种中的一种:
- 区间加:给定(l,r,x),将序列(N)下标(in [l, r])的数加上(x)
- 区间乞降:给定(l,r),讯问下标(in [l,r])的数的和
一种很暴力的主意是对每一个操纵都一遍轮回举行修正、乞降,显然会超时;看到区间乞降很轻易就能够想到前缀和,如许能够把区间乞降降到常数复杂度,但是区间加照样(O(N));这时候就须要线段树上台了(不知道为啥排版变得巨丑,人人将就一下吧)
引见
线段树是一种有用的数据构造,它能够疾速地处置惩罚区间操纵,保护区间信息。线段树是一棵二叉树,它的每一个节点存储的是一个区间的信息(如区间和, 摆布端点等),如下图所示
笔者个人比较习习用构造体来定义每一个节点,假如只开(2N)个节点,有一些状况是不够的,干脆开到(4N),并从上到下,从左向右举行编号,根节点编号为1,其左儿子是2,右儿子是3,以次类推:
#define ls (k << 1) // 左儿子
#define rs (ls | 1) // 右儿子
struct Node {
int l, r, sum, lazy; // l为左端点,r为端点,sum是区间和, lazy是懒标记下文会讲
Node() {}
Node(int _l, int _r, int _sum, int _lazy=0) : l(_l), r(_r), sum(_sum), lazy(_lazy) {}
inline int length() {return r - l + 1; } // 返回区间长度
inline ll mi() { return (l + r) >> 1; } // 返回中心点
} node[N << 2];
保护区间信息
每次更新了较低一层的区间信息时,须要保护其父节点的信息,比方区间信息为区间和(sum)时,保护时父节点的(sum)值即是其摆布儿子的(sum)值的和
inline update(int k) {
node[k].sum = node[ls].sum + node[rs].sum;
}
建立
建立从最上一层节点入手下手向下,一旦碰到叶子节点(区间长度为1的点),申明到最底层了,则返回,再递归地更新其父节点的区间信息
void build(int l, int r, int k) { // k是编号
if(l == r) { // 叶子节点,输入它的值并返回
scanf("%d", &a);
node[k] = Node(l, r, a);
return ;
}
node[k].l = l; node[k].r = r;
int mid = node[k].mi();
build(l, mid, ls);
build(mid + 1, r, rs);
update(k);
}
区间加
(注重辨别守候加的区间([l,r])和节点(k)上的区间([node[k].l, node[k].r])!!)在区间([l,r])上加(addnum):从根节点入手下手,假如我们地点的节点的区间([node[k].l, node[k].r] subseteq [l,r]),那末申明这个节点区间的每一个值都须要被加(addnum);不然,申明节点上的区间没有被完整包括在([l,r])中,假如(r>mid(mid是节点的区间中值)),申明区间([mid + 1, r])这个区间还须要加上(addnum),所以进入右儿子节点;假如(l <= mid),申明区间([l, mid])这个区间还须要加上(addnum),所以进入右儿子节点。须要注重的是,后两种状况完整有大概同时满足。我们再细致斟酌区间加,为了保护线段树使其满足摆布儿子的(sum)之和即是父节点的(sum),将父节点的(sum)更新以后应当要把它的一切子节点都更新,再用一下上面的图,比方说我们让([6, 10])加10,那为了保护线段树,([6, 10])的子节点们都须要加10,统共须要9次加操纵,这造成了一个很严重的问题:如许的区间加以至比暴力还要慢!一个原本是(O(N))的操纵被我们革新成了(O(NlogN)),这时候,一个重要的头脑涌现:懒标记。它的头脑是先仅保护最上一层的区间信息,而耽误对其子节点的更新,如许做的优点在于能够把区间加积累起来,等有须要时将懒标记下传一次性更新子节点,从而有用下降复杂度
inline void push(int k) { // 懒标记下传
node[ls].lazy = node[rs].lazy = node[k].lazy;
node[ls].sum += node[ls].length() * node[k].lazy;
node[rs].sum += node[rs].length() * node[k].lazy;
node[k].lazy = 0;
}
inline void add(int k) {
if(node[k].l >= l && node[k].r <= r) { // 完整包括
node[k].sum += node[k].length() * addnum;
node[k].lazy += addnum; // 懒标记
return ;
}
if(node[k].lazy) push(k); // 下传
if(r > node[k].mi()) add(rs);
if(l <= node[k].mi()) add(ls); // 不能是else if
update(k);
}
区间乞降
区间乞降的步骤基本和区间加一样,代码也是非常相似
inline int query(int k) {
if(node[k].l >= l && node[k].r <= r)
return node[k].sum;
int ans = 0;
if(node[k].lazy) push(k);
if(r > node[k].mi()) ans += query(rs);
if(l <= node[k].mi()) ans += query(ls);
return ans;
}
板子
玩整版开了long long,重要是由于许多题区间一乞降就轻易爆int
#include <cstdio>
#include <cstring>
#include <iostream>
#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
typedef long long ll;
const int N = 1e6+5;
struct Node {
ll l, r, sum, lazy;
Node() {}
Node(ll _l, ll _r, ll _sum, ll _lazy = 0L) : l(_l), r(_r), sum(_sum), lazy(_lazy) {}
inline ll length() { return r - l + 1; }
inline ll mi() { return (l + r) >> 1; }
}node[N << 2];
ll n, m, l, r, addnum;
inline ll read() { // 快读
ll x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
inline void update(int k) {
node[k].sum = node[ls].sum + node[rs].sum;
}
inline void push(int k) {
node[ls].lazy += node[k].lazy;
node[rs].lazy += node[k].lazy;
node[ls].sum += node[k].lazy * node[ls].length();
node[rs].sum += node[k].lazy * node[rs].length();
node[k].lazy = 0L;
}
void build(int l, int r, int k) {
if(l == r) {
ll a = read();
node[k] = Node(l, r, a);
return ;
}
node[k].l = l; node[k].r = r;
build(l, mid, ls);
build(mid + 1, r, rs);
update(k);
}
inline void add(int k) {
if(node[k].l >= l && node[k].r <= r) {
node[k].sum += node[k].length() * addnum;
node[k].lazy += addnum;
return ;
}
if(node[k].lazy) push(k);
if(r > node[k].mi()) add(rs);
if(l <= node[k].mi()) add(ls);
update(k);
}
inline ll query(int k) {
if(node[k].l >= l && node[k].r <= r)
return node[k].sum;
ll ans = 0L;
if(node[k].lazy) push(k);
if(r > node[k].mi()) ans += query(rs);
if(l <= node[k].mi()) ans += query(ls);
return ans;
}
int main() {
n = read(), m = read();
build(1L, n, 1L);
while(m--) {
ll type;
type = read(); l = read(), r = read();
if(type == 2L) // 区间查询
printf("%lldn", query(1L));
else if(type == 1L) { // 区间加
addnum = read();
add(1L);
}
}
return 0;
}
种种类型
最基本的几种
- 区间加 + 区间乞降,这是最基本的线段树,板子题luogu 3372
- 区间乘 + 区间乞降,实在像保护加法懒标记一样,再保护一个乘法的懒标记就能够够了,再轻微改改懒标记下传,板子题luogu 3373
- 区间修正 + 区间求最值,假如没有区间修正,那打个ST就好了(不知道ST的话能够百度一下,许多博客都讲得很清晰),常数还小,有修正就用线段树就行,保护也很简单,取个max就好了
区间加 + 区间求平方之和(或许立方之和)
[ (a_i + x)^2 = a_i^2+2x*a_i+x^2 sum_{i=l}^{r}((a_i+x)^2) = sum_{i=l}^{r}a_i^2+2x*sum_{i=l}^{r}a_i+(l-r+1)*x^2 ]
能够根据上面的公式保护(sum a_i)和(sum a^2_i),立方相似,题目HDU 4578 Transformation
区间开根号(向下取整) + 区间乞降
开根号操纵会让区间里的值变得越发靠近,那只要同时保护区间(max)和(min),假如(max = min),(sum = length * max);假如(max neq min),就暴力地把这个区间上的数都开方,保护懒标记开方次数,且由于一个数(n)最多被开方(logn)次就会变成1,所以每一个数暴力实在最多(O(logn)),不会超时。区间除的头脑也是一样的,由于除法也会使得区间里的值变得越发靠近
例题
但是线段树的许多题都连系了种种技能,如下面这道:
- POJ 2528 Mayor's posters
思绪:离散化+线段树
Flink系统之Table API 和 SQL