本文主要是介绍silent （线段树,详细注解,模板）区间查改，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近学了线段树，打了一个区间加和区间查询的模板
因为打的时候打了很多注解，在网上找模板也没有多少带注解的
理解起来比较困难，所以就发一下博客
题目嘛也就是洛谷P3372
话不多说，上代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1000086;//maxn大小视题目情况而定
int a[MAXN];//存储数据的数组，用来建树
struct Tree
{long long s ;//存储节点值 long long lazy;//当执行区间修改操作时的标记
}tree[MAXN*4];//线段树，长度一般为原数组的四倍，因为无论如何线段树的节点数不会超过原数组四倍
//线段树用的是类似二分的思想，是一颗完全二叉树，有时是满二叉树
inline void build(int now,int l,int r)
{//分别是现在所处的位置和左右端点 if(l==r)//当这个节点储存的区间为lr相等时，它是一个叶子结点 {tree[now].s=a[l];//赋值，l可以换成r，一样的return ;//找到就退出 }int mid=(l+r)/2;//计算出中数build(now*2/*左儿子*/ ,l ,mid);//l是最左边的端点，因为是二叉树，所以中点到最左端点就是左儿子所在位置 build(now*2+1/*右儿子*/,mid+1,r );//理由同上 tree[now].s=tree[now*2].s+tree[now*2+1].s;//叶子结点赋值完之后，会返回到父节点，父节点再把它的儿子的值加起来，循环往复
}//创建线段树,因为a数组已经输入完毕，所以每个叶子结点都要赋值
inline void down(int now,int l,int r)
{int mid=(l+r)/2;tree[now*2 ].s +=tree[now].lazy*(mid-l+1) ;tree[now*2 ].lazy+=tree[now].lazy ;tree[now*2+1].s +=tree[now].lazy*(r-mid/*即r-(mid+1)+1*/);tree[now*2+1].lazy+=tree[now].lazy ;tree[now ].lazy =0;//赋值结束，传递也结束，清零，避免影响下一次操作
}//down函数的作用就是把now的子节点加上他们应该加上的值，并传给子节点lazy，让子节点的子节点也加上这个值
inline void add(int now,int l,int r,int x,int y,long long add_num)
{//区间加，分别是现在所在位置，左右端点， 要修改的区间的左右端点,要给这个区间加上的数 if(l>=x&&r<=y)//当l大于等于x，r小于等于y时，现在所处的结点必然处于区间之内 {tree[now].s +=add_num*(r-l+1);//(r-l+1)求的是这个结点维护了几个数tree[now].lazy+=add_num;//标记懒标,不乘以多少个数的原因是down数组里会乘 return ; }down(now,l,r);//进入down，对子节点进行操作 int mid=(l+r)/2;//求出中点 if(x<=mid)//如果x在中点的左边，很明显要访问左儿子 {add(now*2 ,l,mid,x,y,add_num);}if(y>mid)//不然就是在右边，访问右儿子{add(now*2+1,mid+1,r,x,y,add_num);}//执行完这些之后，下层应该被加过add_num了,但上层还没操作过 tree[now].s=tree[now*2].s+tree[now*2+1].s;//所以要维护一下父节点的值
}
inline long long find(int now,int l,int r,int x,int y)
{//区间查，现在所在的位置，左右端点和要查询的区间的左右端点 if(l>=x&&r<=y)//已经进入查询区间了 {return tree[now].s;//返回要查询区间的值 }down(now,l,r);//处理一下lazy,避免在add的时候有lazy没处理到导致答案错误 int mid=(l+r)/2;//求出中点long long ans=0;//记录答案 if(x<=mid){ans+=find(now*2,l,mid,x,y); }if(y>mid){ans+=find(now*2+1,mid+1,r,x,y);}return ans;
}
int main()
{//如要把区间查和区间加改成单点查和单点加，可以把单点的位置同时传入x和y int n,m;//n个数，m次查询cin>>n>>m;for (int i=1;i<=n;i++){cin>>a[i];} build(1,1,n);//从根节点开始建树int c,l,r,s; for(int i=1;i<=m;i++){cin>>c>>l>>r;if(c==1) {cin>>s;add(1, 1, n, l, r, s);//从根节点开始访问 } else{cout<<find(1, 1, n, l, r)<<endl;//从根节点开始寻找 } }return 0;
}
感谢观看
这篇关于silent （线段树,详细注解,模板）区间查改的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
