线段树简单介绍

一、线段树简介

线段树可以在很小的时间复杂度内实现单点修改、区间修改、区间查询（即区间求和，求区间 max 等）操作。

但是，线段树所维护的信息，需要满足区间加法。

区间加法：如果一个区间 [l,r]（线段树中一个点表示一个区间）满足区间加法的意思是一个区间 [l,r] 的线段树维护的信息（即区间最大值，区间最小值，区间和 等），可以由两个区间 [l,mid]和 [mid+1,r]合并而来。

二、线段树的基本概念
线段树，是一种基于分治思想的二叉搜索树。它支持的所有操作都可以 O(logn)（有的时候可以是O(1) ) 的时间复杂度完成。

但是一旦出现问题，就寄了,，调代码的时间比一般的题目要长很多hh

基本特征：

1.线段树的每一个节点表示一个区间

2.线段树有唯一根，这个根表示的所有会被线段树统计的总区间，一般情况下，跟表示的区间就是 [1,n]

3.线段树的叶子节点表示的区间为 [x,x]，且长度为 1

4. 线段树中如果一个节点表示的区间是 [l,r] ，且这个点不为叶子节点，即 l≠r，那么这个节点的左子树的根表示的区间就是 [l,mid] 这个节点的右子树的根表示的区间就是 [mid+1,r]，其中 mid=⌊l+r⌋ / 2

建立思路：

递归遍历初始区间，把遍历到的所有节点表示的区间记录下来，如果这个节点不是叶子节点（即区间长度大于1），那么就分别遍历左子树和右子树，否则就是叶子节点，不仅要把表示的区间记录下来，还要把线段树维护的信息也记录下来，维护的信息在叶子节点上基本上就是这个数本身

struct Segment_Tree
{
    int l,r;
    LL sum;  
}tr[4 * N];  
void pushup (int u) {  
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build (int u,int l,int r) 
{  
    if (l == r) {
        tr[u] = {l,r,a[l]};
        return ;
    }
    tr[u] = {l,r};  
    int mid = l + r >> 1;
    build (u << 1,l,mid),build (u << 1 | 1,mid + 1,r); 
    pushup (u);  
}

后面的，有时间在更新

嗷嗷嗷~

晚安！