Light Segment Tree

2026.05
C++ Segment Tree Lazy Propagation

轻量线段树模板，采用分层存储，支持区间加和区间求和。

描述

用指针、节点和层级来写线段树很烦。将树的大小设为 $2^n$ 后，可以直接计算每个节点的层级和位置，无需维护树结构，只需一个平铺的 ST-table 数据结构。

该模板使用 st[i][j] 和 lazy[i][j] 分别表示长度为 $2^i$ 的第 $j$ 个区间的区间和与懒标记值。区间使用左闭右开 [l, r) 0-based 索引。

代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1 << 19;	// 524288 > 3e5


void work(){
	vector<i64> a(N);
//	vector<vector<i64>> st(20, vector<i64>(N)); 改用动态建树
	vector<vector<i64>> st, lazy;

	for(int x = N; x; x = x >> 1){
		st.push_back(vector<i64>(x, 0));
		x = x >> 1;
	}
	lazy = st;

#define x getx(l,r)
#define y gety(l,r)
#define mid (l+r)/2

	// 左闭右开 0 base
	// 规定st/lazy[i][j] 表示 [(1<<i * j, 1<<i * (j+1) )
	auto getx = [&](int l, int r)-> int{return log2(r-l);};
	auto gety = [&](int l, int r)-> int{return l / (r - l);};

	// 用左右儿子更新当前节点
	auto pushup = [&](int l, int r) -> void {
		st[x][y] = st[getx(l, mid)][gety(l, mid)] + st[getx(mid, r)][gety(mid, r)];
	};

	// 给当前节点打懒标记
	auto apply = [&](int l, int r, i64 val) -> void {
		st[x][y] += val * (r - l);
		lazy[x][y] += val;
	};

	// 下传懒标记
	auto pushdown = [&](int l, int r) -> void {
		if (lazy[x][y] == 0 || r - l == 1) return;
		i64 val = lazy[x][y];
		apply(l, mid, val);
		apply(mid, r, val);
		lazy[x][y] = 0;
	};

	// 建树
	auto build = [&](auto self, int l, int r) -> void {
		if (r-l == 1) {
			st[0][l] = a[l];
			return;
		}
		self(self, l, mid);
		self(self, mid, r);
		pushup(l, r);
	};

	// 区间加：[ql, qr) += val
	auto update = [&](auto self, int l, int r, int ql, int qr, i64 val) -> void {
		if (qr <= l || r <= ql) return;

		if (ql <= l && r <= qr) {
			apply(l, r, val);
			return;
		}
		pushdown(l, r);
		self(self, l, mid, ql, qr, val);
		self(self, mid, r, ql, qr, val);
		pushup(l, r);
	};

	// 区间查询：[ql, qr) 的和
	auto query = [&](auto self, int l, int r, int ql, int qr) -> i64 {
		if (qr <= l || r <= ql) return 0;
		if (ql <= l && r <= qr) return st[x][y];
		pushdown(l, r);
		return self(self, l, mid, ql, qr) + self(self, mid, r, ql, qr);
	};

#undef x
#undef y
#undef mid

}

int main(){
	ios::sync_with_stdio(false);
	freopen("test.txt", "r", stdin);
	cin.tie(0);
	int T = 1;
	while(T--){
		work();
	}
	return 0;
}