线段树是一种二叉搜索树，什么叫做二叉搜索树，首先满足二叉树，每个结点度小于等于二，即每个结点最多有两颗子树，何为搜索，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。
线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。更可以扩充到二维线段树（矩阵树）和三维线段树（空间树）。对于一维线段树来说，每次更新以及查询的时间复杂度为O(logN)。 完整代码如下：
#include<bits/stdc++.h> //万能头文件 #define ll long long //写着方便 using namespace std; const int N=1e5+1; //数据范围，1e5+1等同于100001 struct node { int l,r,tag;//l:左端点，r：右端点，tag：懒标记 ll pre;//pre:结点的值 }tree[N << 2];//N<<2等同于N*4 ll wth[N];//存储叶节点 void build(int p,int l,int r) //建树 { tree[p].l = l; tree[p].r = r; if(tree[p].l == tree[p].r)//此时区间可看作一个点 { tree[p].pre = wth[r];//赋值，没啥好说 return;//爬回去更新父结点的值 } ll mid = (l+r) >> 1;//二分 if(l <= mid) build(p << 1,l, mid);//递归 if(r > mid) build( (p << 1 | 1), mid + 1, r);//同理，递归 tree[p].pre = tree[p << 1].pre + tree[(p << 1 | 1)].pre;//更新父节结点 } void update(int p)//放懒标记 { tree[p << 1].pre += tree[p].tag * (tree[(p << 1)].r - tree[p << 1].l + 1); tree[(p << 1 | 1)].pre += tree[p].tag * (tree[(p << 1 | 1)].r -tree[(p << 1 | 1)].l + 1); tree[p << 1].tag += tree[p].tag; tree[(p << 1 | 1)].tag += tree[p].tag; tree[p].tag=0; return; } void add(int p,int l,int r,int w)//对区间进行操作 { if(l <= tree[p].l && tree[p].r <= r) { tree[p].pre += w * (tree[p].r - tree[p].l + 1); tree[p].tag += w; return; } if(tree[p].tag) update(p); ll mid = (tree[p].r + tree[p].l)/2;//二分 if(l <= mid) add(p << 1,l,r,w); if(r > mid) add((p << 1 | 1),l,r,w); tree[p].pre = tree[p << 1].pre + tree[(p << 1 | 1)].pre;//更新父结点 } ll ask(int p,int l,int r) { if(l <= tree[p].l && tree[p].r <= r) //判断是否满足 return tree[p].pre; if(tree[p].tag) update(p); ll ans = 0; ll mid = (tree[p].l + tree[p].r) >> 1; if(l <= mid) ans += ask(p << 1,l,r); if(r > mid) ans += ask((p << 1 | 1),l,r); return ans; //返回答案 } int main() { int n,m,opt; //n：元素个数，m：m次询问，opt:操作 int x,y,k;//x，y：区间边界，k：加上的数 scanf("%d%d",&n,&m);//输入 for(int i = 1;i <= n;i++)//循环输入 { scanf("%d",&wth[i]); } build(1,1,n);//调用build函数建树 for(int i = 1;i <= m;i++) { scanf("%d",&opt);//输入操作 if(opt == 1) { scanf("%d%d%d",&x,&y,&k);//操作1 add(1,x,y,k);//调用add函数对区间进行操作 } else{ scanf("%d%d",&x,&y);//操作2 cout<<ask(1,x,y);//调用ask函数询问区间的值 printf("\n");//换行 } } return 0;//结束程序~ }模板推荐：P3372 【模板】线段树 1
