线段树（线段树入门笔记）

什么是线段树
线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

定义结点
一般定义成结构体类型，其成员可以根据需要增加

struct node{
   
   
    int l;//左区间端点 
    int r;//右区间端点 
    int val;//此节点存值 
    int len;//子结点管理区间长度 
}tree[1005];

建树

void build(int cur, int l, int r)
{
   
   
    int mid=(l+r)/2;
    tree[cur].l=l, tree[cur].r=r;
    tree[cur].val=0, tree[cur].len=r-l+1;
    if (l==r)//只有到达叶结点时才把数组的值赋给它 
        tree[cur].val=arr[l];//arr为输入数据的数组
    else{
   
   
        build(cur*2, l, mid);
        build(cur*2+1, mid+1, r);
        tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯过程中更新父结点 
    }
}

单点更新

void updata(int cur, int id, int val)//cur为节点编号，id为修改数据的编号，val为增加的值 
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2;
    if (l==r){
   
   
        tree[cur].val+=val;
        return;
    }
    if (id<=mid)
        updata(cur*2, id, val);
    else
        updata(cur*2+1, id, val);
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯过程中更新父结点 
}

区间查询

int query(int cur, int ql, int qr)
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2, res=0;
    if (ql<=l && r<=qr)//如果此节点的区间在查询区间内，直接返回 
        return tree[cur].val;
    if (ql<=mid)
        res+=query(cur*2, ql, qr);
    if (qr>mid)//注意这里是两个if，不是分支关系 
        res+=query(cur*2+1, ql, qr);
    return res;
}

完整模板

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct node{
   
   
    int l;
    int r;
    int val;
    int len;
    int lazy;
}tree [505];
int arr[505];

void pushup(int cur){
   
   
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
}

void pushdown(int cur){
   
   
    if (tree[cur].lazy!=0){
   
   
        tree[cur*2].lazy+=tree[cur].lazy;
        tree[cur*2+1].lazy+=tree[cur].lazy;
        tree[cur*2].val+=tree[cur*2].len*tree[cur].lazy;
        tree[cur*2+1].val+=tree[cur*2+1].len*tree[cur].lazy;
        tree[cur].lazy=0;
    }
}
//建树 
void build(int cur, int l, int r){
   
   
    int mid=(l+r)/2;
    tree[cur].l=l, tree[cur].r=r;
    tree[cur].val=0, tree[cur].len=r-l+1;
    tree[cur].lazy=0;
    if (l==r)
        tree[cur].val=arr[l];
    else{
   
   
        build(cur*2, l, mid);
        build(cur*2+1, mid+1, r);
        pushup(cur);
    }
}

//单点更新  加值 
void update_point(int cur, int pos, int val)//cur为节点编号，id为修改数据的编号，val为增加的值 
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2;
    if (l==r){
   
   
        tree[cur].val+=val;
        tree[cur].lazy+=val;
        return;
    }
    if (pos<=mid)
        update_point(cur*2, pos, val);
    else
        update_point(cur*2+1, pos, val);
    pushup(cur);
} 
//单点查询
int query_point(int cur, int pos){
   
   
    if (tree[cur].l==tree[cur].r)
        return tree[cur].val;
    pushdown(cur);

    int mid=(tree[cur].l+tree[cur].r)/2;
    if (pos<mid)
        query_point(cur*2, pos);
    else
        query_point(cur*2+1, pos);
} 
//区间查询
int query_interval(int cur, int ql, int qr){
   
   
    if (ql<=tree[cur].l && tree[cur].r<=qr)
        return tree[cur].val;
    pushdown(cur);

    int ans=0;
    int mid=(tree[cur].l+tree[cur].r)/2;
    if (ql<=mid)
        ans+=query_interval(cur*2, ql, qr);
    if (qr>mid)
        ans+=query_interval(cur*2+1, ql, qr);
    return ans; 
} 
//区间更新 加值 
void update_interval(int cur, int l, int r, int val){
   
   
    if (l<=tree[cur].l && tree[cur].r<=r){
   
   
        tree[cur].val+=(tree[cur].r-tree[cur].l+1)*val;
        tree[cur].lazy+=val;
        return;
    }
    pushdown(cur);

    int mid=(tree[cur].l+tree[cur].r)/2;
    if (l<=mid)
        update_interval(cur*2, l, r, val);
    if (r>mid)
        update_interval(cur*2+1, l, r, val);

    pushup(cur);
} 
int main(){
   
   

    return 0;
}

参考链接：
https://blog.csdn.net/zhhe0101/article/details/53871453
https://blog.csdn.net/weixin_40788897/article/details/81539106