一、线段树的应用场景
1.用于解决区间问题，例如求某个区间的和、最大值、最小值。
2.支持的操作有单点修改、区间修改、区间查询。
二、线段树
线段树的核心思想在于：
1.线段树的每个节点预先维护好所对应区间所需要的信息。
2.对于一次查询，将询问区间[L,R]拆分到线段树对应的节点上，通过合并这些节点已经处理好的信息快速得到答案。
3.对于一次单点修改、将其对应的叶子节点到根的所有节点信息更新。
三、线段树代码
以下代码以求区间的最小值为例
1.建树
void build(int x, int l, int r)
{tree[x].l = l;tree[x].r = r;if (l == r){tree[x].value = a[l];return;}int mid = (l + r) / 2;build(2 * x, l, mid);build(2 * x + 1, mid + 1, r);tree[x].value = min(tree[2 * x].value, tree[2 * x + 1].value);
}
2.单点修改
void change(int x, int pos, int w)
{if (tree[x].l == pos && tree[x].r == pos){tree[x].value = w;}int mid = (tree[x].l + tree[x].r) / 2;if (pos <= mid)change(2 * x, pos, w);elsechange(2 * x + 1, pos, w);tree[x].value= min(tree[2 * x].value, tree[2 * x + 1].value);
}
3.区间查询
int query(int x, int l, int r)
{if (tree[x].l == l && tree[x].r == r){return tree[x].value;}int mid= (tree[x].l + tree[x].r) / 2;if (l > mid)return query(2 * x + 1, l, r);else if(r<=mid)return query(2 * x , l, r);else return min(query(2 * x, l, mid),query(2*x+1,mid+1,r));
}
4.区间修改--懒标记
对于区间修改，引入懒标记的概念。在线段树的每个节点加入一个标记，代表该节点对应的区间是否修改。那么对于一次区间操作，仿照之前询问的方法，将要修改的区间[L,R]拆分到线段树的节点上，对相应节点进行整段的修改，同时更新该节点的懒标记。
void update(int x,int w)
{tree[x].value = w;tree[x].lazy_tag = w;
}
void push_down(int x)
{update(2 * x, tree[x].lazy_tag);update(2 * x+1, tree[x].lazy_tag);tree[x].lazy_tag = -1;
}
void push_up(int x)
{tree[x].value= min(tree[2 * x].value, tree[2 * x + 1].value);
}
int change(int x, int l, int r, int w)
{if (tree[x].l == l && tree[x].r == r){update(x, w);return;}if (tree[x].lazy_tag != -1)push_down(x);int mid = (tree[x].l + tree[x].r) / 2;if (l > mid)return change(2 * x + 1, l, r,w);else if (r <= mid)return change(2 * x, l, r,w);else{change(2 * x, l, mid, w);change(2 * x + 1, mid + 1, r, w);};push_up(x);
}
5区间查询--懒标记
int query(int x, int l, int r)
{if (tree[x].l == l && tree[x].r == r){return tree[x].value;}if (tree[x].lazy_tag != -1)push_down(x);int mid= (tree[x].l + tree[x].r) / 2;if (l > mid)return query(2 * x + 1, l, r);else if(r<=mid)return query(2 * x , l, r);else return min(query(2 * x, l, mid),query(2*x+1,mid+1,r));
}