线段树（zr的最爱）
基本长相：
存储
-
每一个节点的编号都对应一个序列的区间
-
按照一个类似完全二叉树的形式存储在数组中
-
对于下标为x的节点,其左儿子下标为$2x$，右儿子下标为$2x+1$，其父亲的下标为$\lfloor{\frac{x}{2}} \rfloor$
-
l,r记录当前节点对应区间的位置，其他变量对应区间信息
-
对于叶子结点: val_i = num_i
-
对于非叶子节点: val_i = val_{ls(i)} + val_{rs(i)}
基本代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int val[4 * N], tag[4 * N];
int rs(int x)
{
return x << 1;
}
int ls(int x)
{
return x << 1 | 1;
}
void push_up(int x)
{
val[x] = val[ls(x)] + val[rs(x)];
}
void work(int x, int l, int ,int k)
{
tag[x] += k;
val[x] += k * (r - l + 1);
}
void push_down(int x, int l, int r)
{
int mid = (l + r) >> 1;
work(ls(x), l, mid, tag[x]);
work(rs(x), mid + 1, r, tag[x]);
//传递tag
tag[x]=0;
//清空tag
}
void build(int x,int l,int r)
{
if(l == r)
{
val[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls[x], l, mid);
build(rs[x], mid+1, r);
push_up(x);
}
int check(int needl, int needr, int l, int r, int x)//区间查询
{//所要查询的左端点 右端点 当前左端点 右端点 当前的节点
int answer = 0;//答案
if(needl <= l && needr>=r)
return val[x];//被包含，返回对应区间的sum
int mid = (l + r) >> 1;
push_down(x, l, r);
if(needl <= mid)
answer += check(needl, needr, l, mid + 1, ls(x));
if(needr > mid)
answer += check(needl, needr, mid + 1, r, rs(x));
//二分递归
return answer;
}
int update(int needl, int needr, int l, int r, int x)//区间修改
{//所要查询的左端点 右端点 当前左端点 右端点 当前的节点
if(needl <= l && needr>=r)
{//被包含
tag[x] += k;
val[x] += k*(r - l + 1);
}
push_down(x, l, r);
int mid = (l + r) >> 1;
if(needl <= mid)
update(needl, needr, l, mid + 1, ls(x));
if(needr > mid)
update(needl, needr, mid + 1, r, rs(x));
//二分递归
push_up(x);
}
signed main()
{
……………………………………………………………………………………
}
大体思想
功能
复杂度
例题
eg1: 线段树 2
思路：
-
若区间乘$k$且完全包含时，则将加法标记，乘法标记，区间和都乘$k$
-
push_up：$val_x$ = val_{ls(x)} + val_{rs(x)}
-
push_down：先下传乘法标记，再下传加法标记乘区间长度(否则乘法标记会被乘两遍)，然后记得清空标记
-
下传乘法标记时：直接下传
-
下传加法标记时：先乘后加
eg2：策略游戏
思路：
-
1.当后手区间内有正有负时，先手取绝对值最小的正/负数，后手取绝对值最大的正/负数
-
2.当后手区间内只有正数/只有负数，先手从最大/最小的正/负数里取，后手从最大值/最小值里取
-
维护每个区间的$max$，$min$，区间有无负数，区间有无正数
-
push_up: minn = min(minn[ls(x)],minn[rs(x)]) , maxx=……，have_neg=have_neg[ls(x)] |have_neg[rs(x)] , have_pos=……
eg3：小白逛公园/Can you answer these queries I/Can you answer these queries III
思路
-
O(n)算法：贪心求最大子段和(但是不能修改)
-
分治做法：将原数列分成等长的两段，递归下去求最大子段和，则原数列最大子段和可能是$\begin{cases} 左半最大子段和 \ 右半最大子段和 \ 跨过分界点的子段和 \end{cases}$
-
sum[x] = sum[ls(x)] + sum[rs(x)] -
maxsum[x] = max(maxsum[ls(x)], maxsum[rs(x)], rsum[ls(x)] + lsum[rs(x)]) -
lsum[x] = max(lsum[ls(x)], sum[ls(x)]+lsum[rs(x)]) -
而区间最长子段和即为$maxsum$
eg4：求区间绝对值之和
思路：
-
开一个变量$sum$记录区间和，$cnt$记录区间内负数个数，$minval$记录区间内最大负数，用$minval$来判断有无负数变成正数,当有负数变成正数时，递归维护区间内负数个数
-
加$k$时，若无正负变化，则区间绝对值和 += (正数个数-负数个数) * $k$，若有正负变化，递归更新新的$minval$以及$cnt$
-
复杂度O(nlogn+mlogn)
eg5：贴海报/铺地板(二维染色)
思路：
扫描线 (求矩形面积并)
小组成员：jjc,spy,spy,gtz,mtx,…………