线段树小记

如题

线段树是一个二叉搜索树，可以将

O(n)

的扫变成

O(log n)

，适用范围很广，可以在线维护修改以及查询区间上的最值，求和。

常看这个

习惯写 pushup：

求区间和的

CPP

void pushup(int t) {
	sum[t] = sum[t << 1] + sum[t << 1 | 1];
}

然后是 pushnow：

CPP

void pushnow(int t, int l, int r, int v) {
	sum[t] += (r - l + 1) * v;
	tag[t] += v;
}

tag 是懒标记，先把 sum 加上该加的，就是子树的和，然后打上懒标记，方便之后往下传。

最后是 pushdown，即往下传懒标记：

CPP

void pushdown(int t, int l, int r) {
	if (!tag[t]) return; // 如果没有懒标记就返回
	int mid = (l + r) >> 1;
	pushnow(t << 1, l, mid, tag[t]);
	pushnow(t << 1 | 1, mid + 1, r, tag[t]);
	tag[t] = 0; // 往子树传完后把自己的懒标记删掉
}

建树：

CPP

void build(int t, int l, int r) {
	if (l == r) {
		sum[t] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(t << 1, l, mid);
	build(t << 1 | 1, mid + 1, r);
	pushup(t);
}

区间修改：

CPP

void modify(int t, int l, int r, int ql, int qr, int v) {
	if (ql <= l && r <= qr) {
		pushnow(t, l, r, v);
		return;
	}
	pushdown(t, l, r);
	int mid = (l + r) >> 1;
	if (ql <= mid) modify(t << 1, l, mid, ql, qr, v);
	if (qr > mid) modify(t << 1 | 1, mid + 1, r, ql, qr, v);
	pushup(t);
}

区间查询：

CPP

int query(int t, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return sum[t];
	pushdown(t, l, r);
	int mid = (l + r) >> 1, res = 0;
	if (ql <= mid) res += query(t << 1, l, mid, ql, qr);
	if (qr > mid) res += query(t << 1 | 1, mid + 1, r, ql, qr);
	pushup(t);
	return res; 
}

然后就可以解决线段树 1 这道题。

文章操作

建树：

区间修改：

区间查询：

相关推荐

评论

线段树小记