什么是线段树
线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶节点[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
