浅谈线段树ROS感到⼗分的惭愧因为我居然来解析这个我看了好久好久的普及组算法并且感到了蒟蒻的⾝份之沉重说实话因为ROS也是最近才算完全学明⽩线段树（最近才盲敲整"棵"线段树），所以硬要说解析的话可能做不到。
ROS是通过洛⾕学会线段树的（本⾝就是个板⼦）（ROS是看学会线段树的）在此先把代码贴这，如果要学习线段树的话强烈建议去看上⾯那篇题解去！讲的很系统很全⾯！虽然我⼀开始看的时候有很多东西没看懂所以ROS在此还是简单讲解⼀下线段树吧（我在此只是讲⼀下我遇到的难点以及我所学习的线段树中的各个函数的意义）如果写的想我上次那篇KMP的解析⼀样详细的话我就累死了⾸先，什么是线段树？上百度百科：只给定义的话可能你⽆法理解线段树的好，所以便需要情景了！（情景见我在上处发的题）在这个情境中，如果我们没有学过线段树的话可能第⼀感觉是直接开数组然后直接⽤最暴⼒的⽅法求解。
emmm看下数据范围，估计这个⽅法能拿30分吧。
但是毕竟NOIP不可能考⼀个线段树的板⼦准确来说，在更多时候线段树只是我们在做题的⼀个⼯具。
所以照某些OIer的话说，我们应该“把线段树刻进DNA中”。
到最后应该做到盲敲线段树的⽔平（然鹅ROS还做不到）所以可能很多OIer的第⼆想法是，分块！（ROS还真的把分块的代码写了⼀下看看能得多少分）写完了结果发现........这道题居然可以⽤分块AC（本来以为第⼆个范围是给分块的分数结果AC了就尴尬）⼝说⽆凭先上图：代码：1 #include<bits/stdc++.h>2#define ll long long3#define N 1000104using namespace std;5 ll n,m,sq,num,_re; //每⼀块有sq个数字，有num个整块6bool yes; //所有块是否为整块，false说明有多余的数字7 ll a[N]; //原数组8 ll tag[N],sum[N]; //tag是lazy标记,sum是这⼀个分块的和9 ll _a,_x,_y,_k;10bool ls(ll x);11bool rs(ll x);12 ll ln(ll x);13 ll rn(ll x);14void update(ll x,ll y,ll z); //x到y所有数均加上k15 ll query(ll x,ll y); //查询x到y所有数的和16 ll belong(ll x);17int main(){18 scanf("%lld%lld",&n,&m);19for(int i=1;i<=n;i++){20 scanf("%lld",&a[i]);21 }22 sq=sqrt(n);23 num=n/sq;24 _re=n%sq;25if(n%sq==0){26 yes=true; //判断是否所有块都是整块27 }28if(!yes){29for(int i=1;i<=num+1;i++){30if(i==num+1){31for(int j=(i-1)*sq+1;j<=n;j++){32 sum[i]+=a[j];33 }34 }35else{36for(int j=(i-1)*sq+1;j<=i*sq;j++){37 sum[i]+=a[j];38 }39 }40 }41 }42else{43for(int i=1;i<=num;i++){44for(int j=(i-1)*sq+1;j<=i*sq;j++){45 sum[i]+=a[j];46 }47 }48 }49for(int i=1;i<=m;i++){50 scanf("%lld",&_a);51if(_a==1){52 scanf("%lld%lld%lld",&_x,&_y,&_k);53 update(_x,_y,_k);54continue;55 }56if(_a==2){57 scanf("%lld%lld",&_x,&_y);58 printf("%lld\n",query(_x,_y));59 }60 }61return0;62 }63 inline bool ls(ll x){64return (x-1)%sq==0?true:false;65 }66 inline bool rs(ll x){67return x%sq==0?true:false;68 }69 inline ll ln(ll x){ //包含的第⼀个整块的下标 70return rs(x)?((x/sq)+1):(ls(x)?((x/sq)+1):(x/sq)+2);71 }72 inline ll rn(ll x){ //包含的最后⼀个整块的下标 73return x/sq;74 }75void update(ll x,ll y,ll z){76 ll left=sq*(ln(x)-1)+1,right=sq*rn(y);77 ll be;78if(x<left){79 be=belong(x);80for(int i=x;i<left;i++){81 a[i]+=z;82 sum[be]+=z;83 }84 }85if(y>right){86 be=belong(y);87for(int i=right+1;i<=y;i++){88 a[i]+=z;89 sum[be]+=z;90 }91 }92 ll ss=z*sq;93 ll _l=ln(x),_r=rn(y);94for(int i=ln(x);i<=rn(y);i++){95 sum[i]+=ss;96 tag[i]+=z;97 }98return ;99 }100 ll query(ll x,ll y){101 ll left=sq*(ln(x)-1)+1,right=sq*rn(y);102 ll _l=ln(x),_r=rn(y);103 ll esp=0;104if(x<left){105for(int i=x;i<left;i++){106 esp+=a[i];107 }108 esp+=tag[belong(x)]*(left-x);109 }110if(y>right){111for(int i=right+1;i<=y;i++){112 esp+=a[i];113 }114 esp+=tag[belong(y)]*(y-right);115 }116for(int i=ln(x);i<=rn(y);i++){117 esp+=sum[i];118 }119return esp;120 }121 ll belong(ll x){122if(x%sq==0){123return x/sq;124 }125else{126return x/sq+1;127 }128 }View Code但这个分块貌似写起来有些问题，写的时候也⽐较随意。
线段树讲解（数据结构、C++）声明：仅⼀张图⽚转载于，⾃⼰画太⿇烦了。
那个博客的讲解也很好，只是他⽤了指针的⽅式来定义线段树，⽽我⽤了结构体，并且他讲了线段树的更⾼级的操作，若对线段树的初级操作不理解，请继续阅读线段树作为⼀种⼗分常⽤的数据结构，在NOIP、NOI中⼴泛的出现，所以在这⾥对线段树进⾏简单的讲解。
线段树⽀持对⼀个数列的求和、单点修改、求最值（最⼤、最⼩）、区间修改（需要lazy标记，暂不讲解）。
这⼏种操作，时间复杂度是（logn）级别的，是⼀种⼗分优秀的数据结构。
因此其获得了⼴泛的应⽤。
定义：顾名思义，它是⼀种树形结构，但每段不是平常所学的⼀个点⼀个点的树，⽽是⼀条⼀条的线段，每条线段包含着⼀些值，其中最主要的是起始和结束点记作 l，r 即左端点和右端点。
那么该如何划分线段树呢？我们采⽤⼆分的思想，即每次将⼀段取半，再进⾏接下来的操作，这样综合了操作的⽅便程度和时间复杂度。
因为线段树通过⼆分得来，所以线段树是⼀颗⼆叉树。
这也⽅便了对⼉⼦查找。
下⾯是线段树的图，有利于理解：建树：仅仅知道模型还是不够的，建树的过程是线段树的关键（build(1,1,n)）从⼀号开始，左端是1，右端是n位运算 i<<1 等效于 i/2 (i<<1)|1 等效于 i/2+1 加速。
inline void update(int i)更新i节点维护的值（求和，最⼤……）{node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum;node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);}inline void build(int i,int l,int r)//inline 还是加速{node[i].l=l;node[i].r=r;//左右端点为当前递归到的 l 和 rif(l==r){//若l==r 则当前的树节点是真正意义上的点node[i].maxx=a[l];//最⼤值就是本⾝的值node[i].sum=a[l];//区间的和就是本⾝的值return;}int mid=(l+r)/2;//因为是⼆叉树所以以中点为分割点build(i<<1,l,mid);//根据⼆叉树的知识，左⼉⼦是i/2右⼉⼦是i/2+1build((i<<1)|1,mid+1,r);update(i);}数列求和：这是线段树的⼀个典型算法，其他的很多应⽤都是从中转化的。
线段树转载请注明出处，谢谢！/metalseed/article/details/8039326持续更新中···一：线段树基本概念1：概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍2：基本操作（demo用的是查询区间最小值）线段树的主要操作有：(1)：线段树的构造void build(int node, int begin, int end);主要思想是递归构造，如果当前节点记录的区间只有一个值，则直接赋值，否则递归构造左右子树，最后回溯的时候给当前节点赋值1.#include <iostream>ing namespace std;3.4.const int maxind = 256;5.int segTree[maxind * 4 + 10];6.int array[maxind];7./* 构造函数，得到线段树 */8.void build(int node, int begin, int end)9.{10. if (begin == end)11. segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */12. else13. {14. /* 递归构造左右子树 */15. build(2*node, begin, (begin+end)/2);16. build(2*node+1, (begin+end)/2+1, end);17.18. /* 回溯时得到当前node节点的线段信息 */19. if (segTree[2 * node] <= segTree[2 * node + 1])20. segTree[node] = segTree[2 * node];21. else22. segTree[node] = segTree[2 * node + 1];23. }24.}25.26.int main()27.{28. array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;29. build(1, 0, 5);30. for(int i = 1; i<=20; ++i)31. cout<< "seg"<< i << "=" <<segTree[i] <<endl;32. return 0;33.}此build构造成的树如图：(2)：区间查询int query(int node, int begin, int end, int left, int right);（其中node为当前查询节点，begin,end为当前节点存储的区间，left,right为此次query所要查询的区间）主要思想是把所要查询的区间[a,b]划分为线段树上的节点，然后将这些节点代表的区间合并起来得到所需信息比如前面一个图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。
把不规则形状切割成n个相同矩形的算法1. 引言在许多工程和科学应用中，需要将不规则形状切割成相同大小的矩形。
这种问题通常出现在计算机辅助设计、图像处理、纺织业和制造业等领域。
如何高效地实现这种不规则形状切割成相同大小的矩形的算法成为一个研究热点。
本文将介绍目前常用的算法和一些最新的研究成果，希望能够对相关领域的研究者和从业者有所帮助。
2. 现有的算法目前，将不规则形状切割成相同大小的矩形的算法主要包括贪心算法、动态规划算法和启发式算法。
这些算法各有优缺点，适用于不同的应用场景。
2.1 贪心算法贪心算法是一种简单且高效的算法，它通常能够在较短的时间内得到一个较优解。
在将不规则形状切割成相同大小的矩形的问题中，贪心算法通常会按照某种规则逐步地将不规则形状切割成矩形，直到形状被完全切割。
然而，贪心算法并不能保证得到的解是最优解，因此在某些情况下可能会得到次优解。
2.2 动态规划算法动态规划算法是一种比较复杂但是能够保证得到最优解的算法。
在将不规则形状切割成相同大小的矩形的问题中，动态规划算法通常会通过建立状态转移方程来逐步计算最优解。
然而，动态规划算法的时间复杂度通常较高，因此在处理较大规模的问题时可能会无法满足实时性的要求。
2.3 启发式算法启发式算法是一种结合了贪心算法和随机搜索的算法，它通常能够在较短的时间内得到一个较优解。
在将不规则形状切割成相同大小的矩形的问题中，启发式算法通常会通过不断地调整切割方式来寻找最优解。
然而，启发式算法并不能保证得到最优解，因此在某些情况下可能会得到次优解。
3. 最新的研究成果近年来，研究人员提出了一些基于深度学习和强化学习的算法，这些算法在解决不规则形状切割成相同大小的矩形的问题上取得了一些突破性的进展。
这些算法通过利用大量的数据和强大的计算能力，能够在较短的时间内得到接近最优解的结果。
然而，这些算法通常需要大量的训练数据和计算资源，因此在实际应用中可能会存在一定的局限性。
