【线段树】动态开点
使用场景
- 维护的区间太大以至于 \(4N\) 存不下，通常是权值线段树；
- 维护的区间下标存在负数；
时间复杂度
- 全部开点，则 \(O(2N - 1)\)
- 每递归一次，最多开点 \(O(\log_N)\) ，若调用 \(M\) 次， \(O(M\log_N)\)
原理
若一段子区间
[L,R]对应的线段树节点为cur，当不需要递归时，就不建点；当调用
addtag()时，新建节点。
注意事项
- 没有
build函数； addtag的节点cur要取址；- 有负数区间时，
mid = (lt + rt - 1) / 2； - 根节点
root为 \(1\)
代码
#include<bits/stdc++.h>
using namespace std;
#define lc(x) tree[x].lc
#define rc(x) tree[x].rc
#define sum(x) tree[x].val
#define tag(x) tree[x].tag
const int N = 1e5 + 5;
int n, m, tot;
long long a[N]
struct node
{
long long tag, val;
int lc, rc;
}tree[N*2];
void addtag(int &cur, int lt, int rt, long long val) //注意取值符
{
if(cur == 0) //结点不存在就新建立
cur = ++tot;
sum(cur) += (rt - lt + 1) * val;
tag(cur) += val;
return ;
}
void pushup(int cur)
{
sum(cur) = sum(lc(cur)) + sum(rc(cur));
return ;
}
void pushdown(int cur, int lt, int rt)
{
if(lt >= rt)
return ;
int mid = (lt + rt - 1) / 2;
addtag(lc(cur), lt, mid, tag(cur));
addtag(rc(cur), mid+1, rt, tag(cur));
tag(cur) = 0;
return ;
}
void update(int cur, int lt, int rt, int qx, int qy, long long val)
{
if(qy < lt || qx > rt) //不归cur管
return ;
if(qx <= lt && rt <= qy) //cur管辖的区间要全部修改，直接打懒标记
{
addtag(cur, lt, rt, val);
return ;
}
pushdown(cur, lt, rt);
int mid = (lt + rt - 1) / 2;
update(lc(cur), lt, mid, qx, qy, val);
update(rc(cur), mid+1, rt, qx, qy, val);
pushup(cur);
return ;
}
long long query(int cur, int lt, int rt, int qx, int qy) //结点、管辖的区间范围、询问的区间范围
{
if(qy < lt || qx > rt)
return 0;
if(qx <= lt && rt <= qy)
return sum(cur);
pushdown(cur, lt, rt);
int mid = (lt + rt - 1) / 2;
return query(lc(cur), lt, mid, qx, qy) + query(rc(cur), mid+1, rt, qx, qy);
}
int main()
{
cin >> n >> m;
int root = 1; //根结点编号
tot = 1; //总结点数量
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
update(root, 1, n, i, i, x);
}
for(int i = 1; i <= m; i++)
{
int opt, x, y, val;
cin >> opt >> x >> y;
if(opt == 1)
{
cin >> val;
update(root, 1, n, x, y, val); //结点编号、管辖的左右边界、修改的左右边界、修改的值
}
else
cout << query(root, 1, n, x, y) << "\n"; //结点编号、管辖的左右边界、询问的左右边界
}
return 0;
}
例题
P5459题解
简要题意
\(n\) 个数，求有多少个区间的和在 \(L\) 和 \(R\) 之间。
思路
本题是求方案树，由题面有关数的和可以得知我们需要一种值域线段树，
注意到 \(L\) 与 \(R\) 的范围较大，所以需要用动态开点解决此类问题，
我们可以先建一个前缀和，自然前缀和 res[] 需要满足 L <= res[j] - res[i] <= R ，可转化为 res[j] - R <= res[i] <= res[j] - L ，
于是，可以以每个前缀为节点，用线段树维护在一个区间中的方案数，
这道题便做完了。
AC 代码
#include<bits/stdc++.h>
using namespace std;
#define lc(x) tree[x].lc
#define rc(x) tree[x].rc
#define sum(x) tree[x].val
#define tag(x) tree[x].tag
const int N = 5e6 + 5;
const long long M = 1e10 + 5;
int n, m, tot;
long long a[N], res[N];
struct node
{
long long tag, val;
int lc, rc;
}tree[N*2];
void addtag(int &cur, int lt, int rt, long long val) //注意取值符
{
if(cur == 0) //结点不存在就新建立
cur = ++tot;
sum(cur) += (rt - lt + 1) * val;
tag(cur) += val;
return ;
}
void pushup(int cur)
{
sum(cur) = sum(lc(cur)) + sum(rc(cur));
return ;
}
void pushdown(int cur, long long lt, long long rt)
{
if(lt >= rt)
return ;
long long mid = (lt + rt - 1) / 2;
addtag(lc(cur), lt, mid, tag(cur));
addtag(rc(cur), mid+1, rt, tag(cur));
tag(cur) = 0;
return ;
}
void update(int cur, long long val, int add, long long L = -M, long long R = M)
{
if(val < L || val > R)
return ;
if(L == R)
{
addtag(cur, L, R, add);
return ;
}
pushdown(cur, L, R);
long long mid = (L + R) >> 1;
update(lc(cur), val, add, L, mid);
update(rc(cur), val, add, mid+1, R);
pushup(cur);
return ;
}
long long query(int cur, long long ql, long long qr, long long L = -M, long long R = M)
{
if(qr < L || ql > R)
return 0;
if(ql <= L && qr >= R)
return sum(cur);
pushdown(cur, L, R);
long long mid = (L + R) >> 1;
return query(lc(cur), ql, qr, L, mid) + query(rc(cur), ql, qr, mid + 1, R);
}
signed main()
{
int ri, le;
cin >> n >> le >> ri;
int root = 1;
tot = 1;
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
res[i] = res[i - 1] + x;
}
long long ans = 0;
update(root, res[0], 1);
for (int i = 1; i <= n; ++i) {
ans += query(root, res[i] - ri, res[i] - le);
update(root, res[i], 1);
}
cout << ans;
return 0;
}