线段树进阶总结一 DFS序欧拉序(括号序)

DFS序

前置的几道题

线段树DFS序 1 单点更新区间查询
https://blog.csdn.net/qq_40831340/article/details/84501232
线段树DFS序 2 区间子树更新单点查
https://blog.csdn.net/qq_40831340/article/details/84501478

以上都是关于统计跟改子树的

欧拉序

这里我们可以处理出关于树上路径的
虽然我觉得都是DFS搞这数组也没有啥大区别

树上操作

https://www.luogu.org/problem/P3178
其实我代码没有过样例能过题的原因是我读错题了样例是父亲指向儿子可是数据全是儿子指向父亲 23333
我可能是出题人以外知道这个事情的人了
这次我们要处理树上路径问题要是像之前2篇博客内样肯定不行我们选择要剪掉 out 的才好
不能再把他们压在一个结构体了当然我之前那样写也是没有想过会有这样的问题

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;

int n, m, val[maxn];
int head[maxn], cnt;
int to[maxn], nxt[maxn];

void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

int seq[maxn << 1], inout[maxn << 1];
int ind[maxn << 1], outs[maxn << 1], tot;

int ss;
void dfs(int u) {
	seq[++ tot] = u, inout[tot] = 1, ind[u] = tot;
	for(int i = head[u]; i; i = nxt[i]) 
		dfs(to[i]),ss ++;
	seq[++ tot] = u, inout[tot] = -1, outs[u] = tot;
}

struct node {
	int sum, lazy, flag;
} tree[maxn << 3];

void push_up(int rt) {
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
	tree[rt].flag = tree[rt << 1].flag + tree[rt << 1 | 1].flag;
}

void push_down(int rt) {
	tree[rt << 1].sum += tree[rt << 1].flag * tree[rt].lazy;
	tree[rt << 1].lazy += tree[rt].lazy;
	tree[rt << 1 | 1].sum += tree[rt << 1 | 1].flag * tree[rt].lazy;
	tree[rt << 1 | 1].lazy += tree[rt].lazy;
	tree[rt].lazy = 0;
}

void build(int l, int r, int rt) {
	if(l == r) {
		tree[rt].flag = inout[l];
		tree[rt].sum = inout[l] * val[seq[l]];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void updata(int L, int R, int l, int r, int rt, int val) {
	if(L <= l && R >= r) {
		tree[rt].sum += tree[rt].flag * val;
		tree[rt].lazy += val;
		return ;
	}
	if(tree[rt].lazy) push_down(rt);
	int mid = l + r >> 1;
	if(L <= mid) updata(L, R, l, mid, rt << 1, val);
	if(R > mid) updata(L, R, mid + 1, r, rt << 1 | 1, val);
	push_up(rt);
}

int query(int L, int R, int l, int r, int rt) {
	if(L <= l && R >= r) {
		return tree[rt].sum;
	}
	if(tree[rt].lazy) push_down(rt);
	int mid = r + l >> 1;
	int res = 0;
	if(L <= mid) res += query(L, R, l, mid, rt << 1);
	if(R > mid) res += query(L, R, mid + 1, r, rt << 1 | 1);
	return res;
}

signed main() {
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i ++ ) scanf("%lld", &val[i]);
	for(int i = 1, a, b; i < n; i ++){
			scanf("%lld %lld", &a, &b), ade(b, a);
	}
	
	int N = n << 1;
	dfs(1);
	build(1, N, 1);
	int op, x, a;

	while(m --) {
		scanf("%lld %lld", &op, &x);
		if(op == 1) {
			scanf("%lld", &a);
			updata(ind[x], ind[x], 1, N, 1, a);
			updata(outs[x], outs[x], 1, N, 1, a);
		} else if(op == 2) {
			scanf("%lld", &a);
			updata(ind[x], outs[x], 1, N, 1, a);
		} else {
			printf("%lld\n", query(1, ind[x], 1, N, 1));
		}
	}
	return 0;
}

树上路径区间查单点改

接下来就是我们 dfs建立括号序列如果让路上某个点+v
路径询问我们增加了多少
就可以考虑根节点到 u 根节点到 v 我们再减去 2倍根节点到 lca 再加上 lca

线段树进阶总结一 DFS序 欧拉序(括号序)

DFS序

欧拉序

树上操作

树上路径 区间查 单点改

全站热榜

线段树进阶总结一 DFS序欧拉序(括号序)

树上路径区间查单点改