线段树

应用广泛的一个数据结构。

要求支持区间加法。（区间合并）

实现

和堆类似，需要使用用数组存二叉树的技巧。
即 $i$ 节点的左右孩子分别为 $2i, 2i+1$ 。
每个节点表示一个区间，常见的写法有闭区间[l, r]或者是左闭右开[l, r)。

建树

void build(int x, int L, int R) {
    //左闭右开[L, R)
    if (L == R - 1) {
        mn[x] = a[L];
        return;
    }
    build(x * 2, L, M);
    build(x * 2 + 1, M, R);
    mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
}

修改

void change(int x, int L, int R, int p, int v) {
    if (L == R - 1) {
        mn[x] = v;
        return;
    }
    int M = (L + R) / 2;
    if (p < M) {
        change(2 * x, L, M, p, v);
    } else {
        change(2 * x + 1, M, R, p, v);
    }
}

询问

void query(int x, int L, int R, int l, int r) {

}

打标记

要求标记可以合并，标记与当前节点无关。常见的标记有

染色/区间修改为同一个值
区间内每个数字 $x \to kx + b$
区间加等差数列/多项式
区间加公比相同的等比数列
区间加Fibonacci数等可以看做矩阵等比数列的东西。

矩形面积并

因为有复杂度大概是 $4n^2$ 的方法，所以很多题并不需要线段树。

可持久化线段树

可以部分替代划分树和归并树等数据结构。

并且更加易于实现，易于调试。

树链剖分

对于树上的问题，可以进一步使用树链剖分解决。

统计的力量

zkw线段树。

和树状数组对比

树状数组的优势在于易于推广到高维，易于实现，常数小。

线段树的优势在于功能强大，只需要支持合并操作即可，可以打标记，可以可持久化。

参考题目

poj 1151
矩形面积并，不需要线段树。

bzoj 1798
维护序列，支持区间加法和乘法。

Luogu P4513
小白逛公园，经典最大子区间和。

Luogu 280D
可以选 $k$ 个的最大子区间和。

Luogu P4145
区间开根号，每个数字会被操作的次数非常少。

bzoj 2957
楼房重建，每次合并区间，需要再在左子树询问一遍。

codechef DGCD
先树链剖分，区间加一个数，区间求gcd。
差分之后转化为区间修改单点查询和单点修改区间询问gcd。

参考资料

《统计的力量》

线段树

segment tree
线段树

区间如何表示？ how to represent an interval
[l, r) 左闭右开 left closed right open
[l, r] 闭区间 closed
二叉树怎么存 how to store the binary tree

x's children are 2*x and 2*x+1, the root is 1
x的孩子是2*x和2*x+1，根节点是1

x's children are 2*x+1 and 2*x+2, the root is 0
x的孩子是2*x+1和2*x+2，根节点是0

(Implementation)
We don't store the right and left endpoints
比较主流的写法：结构体不记录区间左右端点，如果需要通过线段树传下去
void 函数(int 当前节点标号, int 区间左端点，int 区间右端点, ...)
void add/change/query(int current, int left_endpoint, int right_endpoint, int left_query, int right_query)
{
if (left_endpoint > right_query || right_endpoint < left_query) // disjoint
{
return 0;
}
if ()
{
return the information of current node.
}
return query(left ..) + query(right ..)
}

void add/change/query(int current, int left_endpoint, int right_endpoint, int left_query, int right_query)
{
if ()
}

How large should the array be? 4n
空间？开4n

2 * (the smallest power of 2) >= n
稍微精确一点的结果：2 * 大于等于n的最小的2的次幂

n = 100000, 131072

mx[x] = max(mx[x], v);

线段树数组开多大？
4n 或者 8n（矩形面积并的错误写法，不要在叶子节点update）

大小为n的线段树，需要空间是大于等于n的最小的2的次幂 *2

哪些信息可以合并

求和，异或
乘积
min, max, gcd
最大的若干个
矩阵乘法
DP转移

标记和自己无关（所以叶子节点可能有标记，但是完全没有用）

什么样的东西可以当做标记
标记必须可以合并
区间加一个值可以
区间加一个等差数列可以
区间加一个公比相同的等比数列可以
等比数列可以是矩阵的等比数列，比如说Fibonacci数
区间加一个公比不相同的等比数列不可以

264
232
216
28
24
22
2**1

P3372, P3373, P4145, P4513

P3372 【模板】线段树 1
P3373 【模板】线段树 2
P4513
P4145 上帝造题的七分钟2

线段树
Segment Tree

树状数组是只有左孩子的线段树
BIT is Segment Tree with left children only.

线段树不需要区间相减，只需要区间合并
Segment Tree don't need subtraction, but addition (merge)

可以合并的信息 (data which can be merged)
最大值 maximum
次大值 second maximum
最小值 minimum
区间和 sum
出现次数超过一半的众数 majority number

不可以合并的信息 (data which can not be merged)
区间中位数 (median)
区间第k大 (k-th largest)
区间众数 (mode number)

线段树建树保证
节点个数 O(n)
节点总长度 O(n log n)
任意一个区间都可以被 O(log n) 个节点覆盖
任何一个点只被 O(log n) 个节点覆盖

RMQ / Range minimum query
区间最小值

Segment Tree / 线段树
空间 Space O(n)
预处理时间 preprocess time O(n)
求最小值 query O(log n)
可以支持修改 change O(log n)

ST表

笛卡尔树 LCA

RMQ 通过笛卡尔树转化为 LCA
LCA 通过 DFS序转化为 RMQ

最优复杂度都是 O(n) 预处理 O(1) 回答

https://www.spoj.com/problems/RMQSQ/
basic RMQ

https://www.spoj.com/problems/KGSS/
find the largest two in the intervals

http://www.spoj.com/problems/GSS1
http://www.spoj.com/problems/GSS3
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P4513.cpp

4 information
维护4个信息

sum      the sum
sum      总和
leftmax  the interval with max sum, starts at the left point(prefix)
leftmax  从最左开始的最大子段和
rightmax the interval with max sum, ends at the right point(suffix)
rightmax 从最左开始的最大子段和
max      the interval with max sum
max      最大子段和


sm[x] = sm[x*2] + sm[x*2+1]
x的和 等于 x左子树的和 + x右子树的和

lmx[x] = max(lmx[x*2], sm[x*2] + lmx[x*2+1])
x的左最大 等于 x左子树的左最大 和 x左子树的和+x右子树的左最大 中的较大值

rmx[x] = max(rmx[x*2+1], sm[x*2+1] + rmx[x*2])
x的右最大 等于 x右子树的右最大 和 x右子树的和+x左子树的右最大 中的较大值

mx[x] = max(max(mx[x*2], mx[x*2+1]), rmx[x*2] + lmx[2*x+1])
最大子段和 在左子树 在右子树 左子树的右最大+右子树的左最大

convert LCA to RMQ
use dfs order

1 2 2 3 4 4 5 5 3 1 / push pop order
1 2 1 3 4 3 5 3
to query LCA
we want to find the one with least depth.

LCA(2, 4)
min(2, 1, 3, 4) which has the least depth
make_pair(d[x], x)

+-1 RMQ
the preprocess time can be optimize to O(n)
abs(a[i]-a[i-1]) <= 1

convert RMQ to LCA
Cartesian tree

http://poj.org/problem?id=3468
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
// 1 2 6 7 8 9 7 8 9 10
Q 2 4

1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1    b[k]
1 2 3 4 5 6 7 8 9 10   k * b[k]

1 2 6 7 8 9 7 8 9 10
1 1 4 1 1 1 -2 1 1 1
1 2 12 4 5 6 -14 8 9 10

1+2+6+7+8+9 = 7*(1+1+4+1+1+1) - (1+2+12+4+5+6)

difference

a[1] a[2] a[3] .. a[n]
a[0] = 0

b[i] = a[i] - a[i-1]
a[i] = b[1] + b[2] + .. + b[i]

a[1] + a[2] + .. + a[i] = i * b[1] + (i-1) * b[2] + (i-2) * b[3] + ... + 1 * b[i]

$a_1 + a_2 + \cdots + a_i = \sum_{j=1}^{i} a_j = \sum_{j=1}^{i} \sum_{k=1}^j b_k = \sum_{k=1}^{i} (i-k+1)b_k = ib_1 + (i-1)b_2 + \cdots + 1b_i$

$\sum_{k=1}^{i} (i-k+1)b_k = (i+1)(\sum_{k=1}^{i}b_k) - (\sum_{k=1}^{i}kb_k)$

We need two BIT to maintain the prefix sum of $b_k$ and $k b_k$ .
https://www.luogu.com.cn/blog/Start-Dash/P3372

The lazy tag has nothing to do with itself
标记和自己无关

The lazy tag must be able to be merged.
标记必须可以合并

常见可以合并的标记
mergeable:

区间 += d，区间增加
addition (add the same value)
区间 *= d，区间乘法
multiplication
区间 = d，区间赋值
assignment
区间翻转，0变成1，1变成0
change 0 to 1, change 1 to 0
区间 += 等差数列，a[l] += 1, a[l+1] += 2, a[l+2] += 3, ...
add arithmetic sequence (any common differences)
公比相同的等比数列，等比数列是广义的等比数列，比如Fibonacci也算等比数列
geometric sequence (the same common ratio)
区间加法区间乘法
addition and multiplication (change x to k x + b)

x -> k1 x + b1
x -> k2 x + b2

x -> (k2 (k1 x + b1) + b2)
x -> k1 k2 x + (k2 b1 + b2)

1x + 0

2
1x + 2

2
2x + 4

2
2x

2
2x + 2

不可以合并的标记
non-mergeable

公比不同的等比数列
geometric sequence (different common ratio)

The lazy tags on leafs is useless.
it has nothing to do with itself, and can't be pushed down.
叶子节点的标记是没有用的，因为标记和自己无关，标记没有办法继续向下推

leafs and the query interval are either disjoint or contained.
对于叶子节点，和询问区间的关系，要么相离，要么包含

For some simple lazy tags, some implementations don't push them down.
对于一些简单的标记，有不推标记的写法（可以忽略）

区间先+2，再+3，相当于+5
区间先2，再3，相当于*6

能不能既支持加法，又支持乘法？

顺序问题
区间先+2，再2 x->2x+4
区间先2，再+2 x->2x+2

标记：k x + b 记录k和b

k2(k1 x + b1) + b2
k1k2 x + (b1 k2 + b2)

https://www.luogu.com.cn/problem/P3373
5 5 38
1 5 4 2 3
2 1 4 1 // 2 6 5 3 3
3 2 5 // 6+5+3+3 = 17
1 2 4 2 // 2 12 10 6 3
2 3 5 5 // 2 12 15 11 8
3 1 4 // 2+12+15+11 = 40%38 = 2

https://www.spoj.com/problems/GSS4/
https://www.luogu.com.cn/problemnew/solution/P4145
(Another solution: USE union find set to jump 1s, and use BIT to maintain the sum)
5
1 2 3 4 5
5
1 2 4 // 9
0 2 4 // 1 1 1 2 5
1 2 4 // 4
0 4 5 // 1 1 1 1 2
1 1 5 // 6

2**1 开1次根号变到1 sqrt(2**1) = 1
2**2 开2次根号变到1 sqrt(sqrt(2**2)) = 1
2**4 开3次根号变到1 sqrt(sqrt(sqrt(2**4))) = 1
2**8 开4次根号变到1 sqrt(sqrt(sqrt(sqrt(2**8)))) = 1
2**16 开5次根号变到1 sqrt(sqrt(sqrt(sqrt(sqrt(2**16))))) = 1
2**32 开6次根号变到1 sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(2**32)))))) = 1
2**64 开7次根号变到1  sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(2**64))))))) = 1
2**64 > 1e18

sqrt(x) = x
void change(int x, int l, int r, int L, int R)
{
if (s[x] == r - l + 1)
{
return;
}
}

http://usaco.org/index.php?page=viewproblem2&cpid=865

LIS
longest increasing subsequence

1 4 7 2 5 8 3 6 9

use binary search

f[i] = the minimum of the last one of some LIS with length i
f[i] is increasing
when a new element added, f[i] changes at most 1 postion

0 x x x x x x
0 1 x x x x x
0 1 4 x x x x
0 1 4 7 x x x
0 1 2 7 x x x
0 1 2 5 x x x
0 1 2 5 8 x x
0 1 2 3 8 x x
0 1 2 3 6 x x
0 1 2 3 6 9 x

length of LIS is 5

https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P1020.cpp

Another important application:
use the minimum number of increasing sequences to cover a sequence /
divide the given sequence into minimum number of increasing sequences

the answer is the length of longest decreasing sequence.
because any two numbers in the longest decreasing sequence can not be in the same increasing sequence

use data structure

f[i] = the longest LIS which the last element is i

read x
f[x] = max(f[1], f[2] ... f[x]) + 1
we will use BIT or segtree.
BIT

only change smaller to larger.
only query prefix

next problem:
what is the number of Longest Increasing Subsequences
https://www.cnblogs.com/DOLFAMINGO/p/8719525.html

f[i] = (the length of the longest LIS which the last element is i, the number of ...)

If the lengths are the same, sum the number of plans up.
If the lengths are different, choose the longest one.

We want delete the k-th smallest subset == the k-th largest subset remains.
Find the k-th largest LIS.

For each element, start with this element, the length / number of plans of LIS.

3 2 1 6 5 4 9 8 7

7: (length 1, plans: 1)
8: (length 1, plans: 1)
9: (length 1, plans: 1)
4: (length 2, plans: 3)
5: (length 2, plans: 3)
6: (length 2, plans: 3)
1: (length 3, plans: 9)
2: (length 3, plans: 9)
3: (length 3, plans: 9)

If one element is in the LIS, then its position is unique.
find the 14-th largest LIS

3 ? NO. 14 -= 9 -> 5
2 ? YES. 5 <= 9

6 ? NO. 5 -= 3 -> 2
5 ? YES. 2 <= 3

9 ? NO. 2 -= 1 -> 1
8 ? YES. 1 <= 1

14-th largest LIS. 2 5 8
https://www.luogu.com.cn/blog/Mirach/solution-p5156

#include <bits/stdc++.h>
typedef long long ll;

inline void read(int&x){
    char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
    while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}

const int N=101000;
struct Edge{int v,nxt;}e[N];
int a[N],chs[N],head[N];
int n,_;ll k;

const ll lim=1e18;

struct node{
    int v;ll c;
    // v is length
    // c is the number of plans
    inline node(){}
    friend inline void operator + (node&A,const node B){
    	// v
        if(A.v<B.v)A.v=B.v,A.c=B.c;
        else if(A.v==B.v)A.c=std::min(lim,A.c+B.c);
    }
}d[N],g[N],cl;

#define lb(x) (x&(-x))

inline node qy(int x){node p=cl;for(x;x<=n+1;x+=lb(x))p+d[x];return p;}
// query is special, x += lowbit(x)
inline void add(int x,node y){for(;x;x-=lb(x))d[x]+y;}
// add is special, x -= lowbit(x)
inline void ae(int u,int v)
{e[++_].v=v,e[_].nxt=head[u],head[u]=_;}
// adjcent list

int main(){
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i)read(a[i]);
    cl.c=1,add(n+1,cl),cl.c=0;
    for(int i=n;i;--i){ // from last one to the first one
        g[i]=qy(a[i]);  // query suffix the one after a[i] must be >= a[i]
        ++g[i].v; // increase the length by 1
        add(a[i],g[i]); // add it back
    }
    for(int i=n;i;--i) // backward
    	ae(g[i].v,i); // i is the value
    	// the last added, is the first visied
    // vector[length].push_back(index);
    // qy(1).v is the length of LIS
    for(int stp=qy(1).v,R=0;stp;--stp) // for length from max to 1
    {
	    for(int i=head[stp],v;i;i=e[i].nxt){ // try every possible elements.
	    	// be careful about the order.
	        v=e[i].v;
	        // e[i].v means value, the value is index
	        // v is the index
	        if(g[v].c<k)
	        {
	        	// the number of plans are not enough
	        	k-=g[v].c;
	        }
	        else
	        {
	        	// it's enough, try next length.
	        	// v is index
	            chs[a[v]]=true;
	            // v is the index, a[v] is the value
	            // a[v] should not be printed
	            while(R<v)
	            {
	            	g[R++]=cl;
	            	// cl means clear
	            	// clear all postions before v // the next one must after v
	            }
	            break;
	        }
	    }
    }

    printf("%d\n",n-qy(1).v);
    // n - the length of LIS
    for(int i=1;i<=n;++i)
        if(!chs[i])printf("%d\n",i);
        // output iff chs[i]==0
    return 0;
}

https://www.luogu.com.cn/blog/milkfilling/solution-p3373

P1471 方差
不止维护一次方和，还维护0次方和，2次方和。

方差 = 平方的平均数 - 平均数的平方

区间长度 s0
区间和 s1
区间平方和 s2
区间立方和 s3
区间加k之后，上面3个值是怎么变的？

new s0 = s0
new s1 = s1 + s0 * k
new s2 = s2 + 2 s1 * k + s0 * k * k
new s3 = s3 + 3 s2 * k + 3 * s1 * k * k + s0 * k * k * k

1 * C(n, 1) + 15 * C(n, 2) + 50 * C(n, 3) + 60 * C(n, 4) + 24 * C(n, 5)

2 ** 64 -> 2 ** 32 -> 2 ** 16 -> 2 ** 8 -> 2 ** 4 -> 2 ** 2 -> 2 ** 1 -> 1

a[i]

b[i] = a[1] + a[2] + ... + a[i]
c[n] = b[1] + b[2] + ... + b[n]
c[n] = na[1] + (n-1)a[2] + ... + 1a[n]
c[n] = (n+1)(a[1] + a[2] + a[3] + .. + a[n]) - (1a[1] + 2a[2] + 3a[3] + ...na[n])

P4513 小白逛公园
SP1043 GSS1 - Can you answer these queries I
SP1716 GSS3 - Can you answer these queries III
SP2916 GSS5 - Can you answer these queries V

P5156 [USACO08FEB]Hotel G
每个子树 / 线段树的中间节点，
维护
从左边向右最多连续多少个0
从右边向左最多连续多少个0
当前子树最长一段全是0的区间是多长

懒惰标记
区间内是不是全是 0 或 1

P3097 [USACO13DEC]Optimal Milking G

1 2 3 4 5

1 2 3 4 2
2+4 = 6
1 7 3 4 2
7+4 = 11
10 7 3 4 2
10+3+2 = 15

必须不选最左边的 && 必须不选最右边的 0
必须不选最左边的 && 必须选最右边的 1
必须选最左边的 && 必须不选最右边的 2
必须选最左边的 && 必须选最右边的 3

f[x][0] = max(f[2 * x][0] + f[2 * x + 1][0], f[2 * x][0] + f[2 * x + 1][2], f[2 * x][1] + f[2 * x + 1][0])

f[x][i] = max()
f[2 * x][i & 2] + f[2 * x + 1][i & 1] // 左子树最右和右子树最左都不选
f[2 * x][i & 2] + f[2 * x + 1][i | 2] // 左子树最右不选和右子树最左选
f[2 * x][i | 1] + f[2 * x + 1][i & 1] // 左子树最右选和右子树最左不选

必须不选最左边的 && 必须不选最右边的
必须不选最左边的 && 最右边的选不选都可以
最左边的选不选都可以 && 必须不选最右边的
最左边的选不选都可以 && 最右边的选不选都可以

f[x][3] = max(f[x][3], f[x][2], f[x][1], f[x][0])
f[x][2] = max(f[x][2], f[x][0])
f[x][1] = max(f[x][1], f[x][0])

21 开1次根号变到1
22 开2次根号变到1
24 开3次根号变到1
28 开4次根号变到1
216 开5次根号变到1
232 开6次根号变到1
2**64 开7次根号变到1

P5490 【模板】扫描线
扫描线，线段树求矩形面积并

矩形面积并的线段树不推标记

P6098 [USACO19FEB]Cow Land G
修改一个点的点权
询问一个点到根节点路径上所有点权的xor
询问一个点的点权

DFS序和树状数组/线段树

问一个点到根节点的权值之和
进栈的位置 +=
出栈的位置 -=
询问x到根节点的情况，问开始到 x进栈的位置
问一个点的子树之和
进栈的位置 += 1

问子树求和
http://poj.org/problem?id=3321 Apple Tree
子树在DFS序中是连续的一段
进出栈DFS序

1 2 3 4 5
1 1
22
3 3
44
55
1 2 2 3 4 4 5 5 3 1
长度为2n，每个点恰好出现2次

http://usaco.org/index.php?page=viewproblem2&cpid=624

Eulerian Path

http://usaco.org/index.php?page=viewproblem2&cpid=816
Slingshots

divide into 4 parts
use segtree/BIT/map to find the max/min of prefix/suffix

https://www.luogu.com.cn/problem/P6119
[USACO17FEB]Why Did the Cow Cross the Road II G

LCS longest common subsequence
special case:
the LCS of two permutations is the same as LIS

3 2 1 6 5 4
2 1 4 3 6 5
change the number to the number
1 2 3 4 5 6
2 3 6 1 4 5
for the second line, any increasing subsequence is a common subsequence.
Time Complexity is O(n log n)

another special case:
any number occurs at most twice.
a[]: 1 1 2 2 3 3
b[]: 1 2 3 1 2 3

(1, 1) // a[1] == b[1]
(2, 1) // a[2] == b[1]
(1, 4)
(2, 4)
(3, 2)
(4, 2)
(3, 5)
(4, 5)
(5, 3)
(6, 3)
(5, 6)
(6, 6)

sort these points by x, if x is the same, greater y comes first
bool cmp(Point a, Point b)
{
return a.x < b.x || (a.x == b.x && a.y > b.y);
}

(1, 4)
(1, 1)
(2, 4)
(2, 1)
(3, 5)
(3, 2)
(4, 5)
(4, 2)
(5, 6)
(5, 3)
(6, 6)
(6, 3)

find the longest increasing (not non-decreasing) subsequence, which is the length of LCS.

[USACO11DEC]Grass Planting G

in a tree
change a path, query a vertex is the same as
change a vertex, query a subtree // use DFS order and BIT

change a subtree, query a vertex is the same as
change a vertex, query a path // use DFS order and BIT

http://usaco.org/index.php?page=viewproblem2&cpid=722
4 3 2 1 1 4 2 3

2D version
sort 1D, use BIT/segtree for 1D

3D version
sort 1D, use 2D segtree
CDQ D&C

change one position, query the sum

sort them
(first_occur[x], second_occur[x], x)

4 1

4
3
2
1

1
4
2
3

(1, 2, 4)
(2, 4, 3)
(3, 3, 2)
(4, 1, 1)

https://www.luogu.com.cn/blog/27-43wyy/solution-p3658

// query friendly crossings

// the (friendly) inversion caused by (4 and something) sum(d[2..n][4-k..4+k]) = 0
// the inversion caused by (4 and something) sum(d[2..n][...]) = 0
change(2, 4, 1) // d[2][4] += 1

// the (friendly) caused by (4 and something) sum(d[4..n][3-k..3+k]) = 0
// the inversion caused by (4 and something) sum(d[4..n][...]) = 0
change(4, 3, 1) // d[4][3] += 1

// the (friendly) caused by (4 and something) sum(d[3..n][2-k..2+k]) = 1
// the inversion caused by (4 and something) sum(d[3..n][...]) = 1
change(3, 2, 1) // d[3][2] += 1

// the (friendly) caused by (4 and something) sum(d[1..n][1-k..1+k]) = 1
// the inversion caused by (4 and something) sum(d[1..n][...]) = 3
// 2 unfriendly crossings
change(1, 1, 1) // d[1][1] += 1

for (int i = 0; i < n; i++)
{
change(second_occur[a[i].second], a[i].third, 1);
query()
}

https://www.luogu.com.cn/problem/P1531
最基础的线段树

单点修改
区间最大

spoj SPAM_ATX

https://www.spoj.com/problems/SPAM_ATX/

线段树扫描线
Luogu P5490

这些楼里能看到几个
最高的一个楼是什么

对比线段树树状数组
树状数组快一点，好写一点

树状数组支持高维

线段树只需要支持区间合并