【线段树】动态开点

使用场景

  1. 维护的区间太大以至于 \(4N\) 存不下，通常是权值线段树；
  2. 维护的区间下标存在负数；

时间复杂度

  1. 全部开点，则 \(O(2N - 1)\)
  2. 每递归一次，最多开点 \(O(\log_N)\) ，若调用 \(M\) 次， \(O(M\log_N)\)

原理

  1. 若一段子区间 [L,R] 对应的线段树节点为 cur ，当不需要递归时，就不建点；

  2. 当调用 addtag() 时，新建节点。

注意事项

  1. 没有 build 函数；
  2. addtag 的节点 cur 要取址；
  3. 有负数区间时， mid = (lt + rt - 1) / 2；
  4. 根节点 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;
}

例题

Luogu P3372

Luogu P2781

Luogu P5459

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;
}
标签 , , ,