线段树

线段树（Segment Tree）是一种基于分治思想的二叉树结构，主要用于维护区间信息。
与树状数组相比，它可以实现在$O(\log n)$内对原序列区间修改，还同时支持多种操作（要求满足结合律，如：加、乘），更具通用性。

该结构满足以下性质：

1. 线段树的每个节点都代表一个区间，存储区间内的统计值

2. 线段树具有唯一的根节点，其代表的区间是整个统计范围，如$[1, N]$

3. 线段树的每个叶子节点都代表一个长度为1的元区间$[x, x]$

4. 对于每个内部节点$[l, r]$，它的左子节点是$[l ,mid]$，右子节点是$[mid + 1, r]$，其中$mid = \left \lfloor \frac{l + r}{2} \right \rfloor $

   不难发现，左子节点对应的区间长度，与右节点相同或者比之恰好多1

线段树

不带懒标记的线段树支持O(log n)的单点更新，完全可以用树状数组替代，树状数组还更省空间。

所以实际用处不大。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

using int64 = long long;

const int N = 1e5 + 7;

struct SegmentTree {
    #define lc rt << 1
    #define rc rt << 1 | 1
	int64 sum[N * 4];
	void conv(int rt, int l, int r, int d) {
		sum[rt] += d * (r - l + 1);
	}
	void up(int rt) {
		sum[rt] = sum[lc] + sum[rc];
	}
	void update(int rt, int l, int r, int pos, int d) {
        if (l == pos && r == pos) {
            conv(rt, l, r, d);
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) update(lc, l, mid, pos, d);
        if (pos > mid) update(rc, mid + 1, r, pos, d);
        up(rt);
	}
	int64 query(int rt, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[rt];
		}
		int64 res = 0;
		int mid = l + r >> 1;
		if (L <= mid) res += query(lc, l, mid, L, R);
		if (R > mid) res += query(rc, mid + 1, r, L, R);
		return res;
	}
};

不带懒标记的线段树可以支持O(n)的区间修改，但这样往往不能满足题目需求。

带懒标记的线段树

带懒标记的线段树可以支持O(log n)的区间修改

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

using int64 = long long;

const int N = 1e5 + 7;

struct SegmentTree {
    #define lc rt << 1
    #define rc rt << 1 | 1
	int64 sum[N * 4], tag[N * 4];
	void conv(int rt, int l, int r, int d) {
		sum[rt] += d * (r - l + 1);
		tag[rt] += d;
	}
	void up(int rt) {
		sum[rt] = sum[lc] + sum[rc];
	}
	void down(int rt, int l, int r) {
		int64& d = tag[rt];
		int mid = l + r >> 1;
		conv(lc, l, mid, d), conv(rc, mid + 1, r, d);
		d = 0;
	}
	void update(int rt, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			conv(rt, l, r, d);
			return;
		}
		down(rt, l, r);
		int mid = l + r >> 1;
		if (L <= mid) update(lc, l, mid, L, R, d);
		if (R > mid) update(rc, mid + 1, r, L, R, d);
		up(rt);
	}
	int64 query(int rt, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[rt];
		}
		down(rt, l, r);
		int64 res = 0;
		int mid = l + r >> 1;
		if (L <= mid) res += query(lc, l, mid, L, R);
		if (R > mid) res += query(rc, mid + 1, r, L, R);
		return res;
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int>a(n + 1); // 1-based, n个数组成数组

	SegmentTree segt;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		segt.update(1, 1, n, i, i, a[i]);
	}

	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			int k;
			cin >> k;
			segt.update(1, 1, n, x, y, k);
		}
		else {
			cout << segt.query(1, 1, n, x, y) << '\n';
		}
	}
}

动态开点线段树

zkw线段树（非递归）

非递归线段树，是一种代码较短、常数较小的线段树写法。

因为张昆玮在《统计的力量》中介绍了这种数据结构，因此常常被称为zkw线段树，