# 線段樹

（重定向自线段树

## 結構

${\displaystyle (-\infty ,x_{1}),[x_{1},x_{1}],(x_{1},x_{2}),[x_{2},x_{2}],...,(x_{m-1},x_{m}),[x_{m},x_{m}],(x_{m},+\infty )}$

• 其每一個葉節點，從左到右代表每個單位區間。
• 其內部節點代表的區間是其兩個兒子代表的區間之聯集。
• 每個節點（包含葉子）中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N))，則節點N中會儲存線段S。

## 基本操作

### 节点数据向上更新

/* 对于区间求和 */
void push_up(int rt) {
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

/* 对于区间求最大值 */
void push_up(int rt) {
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}


### 节点懒惰标记下推

void push_down(int rt, int len) {
tree[rt << 1] += lazy[rt] * (len - (len >> 1));
lazy[rt << 1] += lazy[rt];
tree[rt << 1 | 1] += lazy[rt] * (len >> 1);
lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}


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


### 建树

#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void build(int rt = 1, int l = 1, int r = N) {
if (l == r) { std::cin >> tree[rt]; return; }
int m = (l + r) >> 1;
build(lchild); build(rchild);
push_up(rt);
}


### 更新

#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void update(int p, int delta, int rt = 1, int l = 1, int r = N) {
if (l == r) {
tree[rt] += delta;
return;
}
int m = (l + r) >> 1;
if (p <= m) update(p, delta, lchild);
else update(p, delta, rchild);
push_up(rt);
}


#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void update(int L, int R, int delta, int rt = 1, int l = 1, int r = N) {
if (L <= l && r <= R) {
tree[rt] += delta * (r - l + 1);
lazy[rt] += delta;
return;
}
if (lazy[rt]) push_down(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, delta, lchild);
if (R > m)  update(L, R, delta, rchild);
push_up(rt);
}


### 区间查询

#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
int query(int L, int R, int rt = 1, int l = 1, int r = N) {
if (L <= l && r <= R) return tree[rt];
if (lazy[rt]) push_down(rt, r - l + 1);
int m = (l + r) >> 1, ret = 0;
if (L <= m) ret += query(L, R, lchild);
if (R > m)  ret += query(L, R, rchild);
return ret;
}


## 变种

zkw线段树是一种自底向上的线段树，由清华大学的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数[2]

## 相关链接

http://dongxicheng.org/structure/segment-tree/页面存档备份，存于互联网档案馆https://cp-algorithms.com/data_structures/segment_tree.html页面存档备份，存于互联网档案馆） Segment Tree – CP-Algorithms

### 可直接使用的编程模板

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

namespace SegTree {
#define maxn 1000000
class SegmentTree {
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
public :
int addv[maxn], maxv[maxn], minv[maxn], sumv[maxn];
int arr[maxn];
int N;
private:int _max(const int& _, const int& __) { return _>__?_:__; }
private:int _min(const int& _, const int& __) { return _<__?_:__; }
public : int pushup(int o) {
minv[o] = _min(minv[lson], minv[rson]);
maxv[o] = _max(maxv[lson], maxv[rson]);
sumv[o] = sumv[lson] + sumv[rson];
return 0;
}
public : int pushdown(int o, int l, int r) {
if(addv[o] == 0) return -1;
sumv[lson] += addv[o] * (mid-l+1); sumv[rson] += addv[o] * (r-mid);
}
public : int Build(int o, int l, int r) {
if(l == r) {
maxv[o] = arr[l];minv[o] = arr[l];sumv[o] = arr[l];
return 0;
}
Build(lson, l, mid);
Build(rson, mid+1, r);
pushup(o);
return 0;
}
public : int optadd(int o, int l, int r, int ql, int qr, int addval) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
sumv[o] += addval * (r-l+1);
return 0;
}
pushdown(o, l, r);
pushup(o);
}
public : int query_sum(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return sumv[o];
}
pushdown(o, l, r);
return query_sum(lson, l, mid, ql, qr) + query_sum(rson, mid+1, r, ql, qr);
}
public : int query_min(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return minv[o];
}
pushdown(o, l, r);
return _min(query_min(lson, l, mid, ql, qr), query_min(rson, mid+1, r, ql, qr));
}
public : int query_max(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return maxv[o];
}
pushdown(o, l, r);
return _max(query_max(lson, l, mid, ql, qr), query_max(rson, mid+1, r, ql, qr));
}
};
}
//End of SegmentTree
using namespace SegTree;


## 參考資料

1. ^ de Berg 等人 2000，p.229）
2. ^ 张昆玮. 统计的力量——线段树全接触. [2021-10-30]. （原始内容存档于2021-11-04）.