线段树(超详细!!!)

线段树上每个节点维护了它所对应的区间的最小值。我们可以用简单的递归来得到这棵初始线段树,即用build(k,l,r)来表示当前要构建区间[l,r]的线段树,k表示区间[l,r]所对应的标号,若l=r则我们可以直接构建一个叶节点,它的区间最小值就是al;否则我们新建一个节点,它的两个子节点可以通过build(k*2,l,mid)与build(k*2+1,mid+1,r)来递归得到,它的区间最小值就是两个儿子的区间最小值中的较小者。因为节点个数是n*2级别的,所以这个过程是O(n)级别的。

需要特别注意的是,用上述标号方法,线段树的数组要开到4*n级别。

【代码实现】void build(int k,int l,int r) //k表示当前节点的编号,l,r为当前节点所代表                  {                                               的区间  
    if(l==r)                              //当前节点为叶子节点  
    {    
        mi[k]=a[l];       //对应区间的最小值为原序列中的对应值  
        return;    
    }    
    int mid=(l+r)/2;     
    build (k*2,l,mid);               //构造左子树  
    build (k*2+1,mid+1,r);      //构造右子树  
    mi[k]=min(mi[k*2],mi[k*2+1]);   //自下向上更新  
}   

单点修改操作

举个栗子:如下图

假设要将a0修改为2,那么我们只需要重新计算下图所示的4个节点信息:

【代码实现】
void change(int k,int l,int r,int x,int v)   //x为原序列的位置,v为要改为的值
{
     if(l==r&&l==x)                    //当前节点为对应的叶子节点
     {  mi[k]=v; return; }                    //修改叶子节点
     int mid=(l+r)/2;
     if(x<=mid) change(k*2,l,mid,x,v);           //修改左子区间
     if(x>mid) change(k*2+1,mid+1,r,x,v);  //修改右子区间
     mi[k]=min(mi[k*2],mi[k*2+1]);  //更新相关的值
} 

区间询问操作

若要询问区间[0,6],我们只需要用到下图中的三个节点的信息:

考虑怎样提取这些区间。我们可以递归处理这个求解过程:初始时访问根节点。接下来当前访问节点所对应区间与询问区间的关系有三种情况:

(1)当前区间与询问区间完全无交集,那么此时可以直接返回一个不影响答案的极大值,不继续递归(因为子节点肯定也与询问区间无交集)。

(2)询问区间完全包含当前区间,那么直接返回当前节点所维护的区间最小值(因为这段区间的信息都在这个节点维护好了,不需要递归下去求解)。

(3)除了上面两种情况,我们对两个儿子递归处理,返回两个结果中的较小值。

【代码实现】
int query_min(int k,int l,int r,int x,int y)  
        //k当前节点,x,y为询问区间,l,r为当前节点维护区间
{  
    if(y<l||x>r) return 2147483647;//若与询问区间完全无交集,返回一个极大值
    if(x<=l&&r<=y) return mi[k];  //询问区间在当前区间,返回维护好的最小值
    int mid=(l+r)/2;    
    return min(query_min(k*2,l,mid),query_min(k*2+1,mid+1,r));    
                              //否则分别处理左子区间和右子区间
} 

小试牛刀——

1547:【 例 1】区间和

【题目描述】

给定一个全0数列,规定有两种操作,一是修改某个元素,二是求区间的连续和。

【输入】

输入数据第一行包含两个正整数n,m(n≤100000,m≤500000)以下是m行, 每行有三个正整数k,a,b (k=0或1,a,b≤n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。

【输出】

对于每个询问输出对应的答案。

【输入样例】

10 20 0 1 10 1 1 4 0 6 6 1 4 10 1 8 9 1 4 9 0 10 2 1 1 8 0 2 10 1 3 9 0 7 8 0 3 10 0 1 1 1 3 8 1 6 9 0 5 5 1 1 8 0 4 2 1 2 8 0 1 1

----(乱入:格式不太多请多见谅(o´ω`o)?)

【输出样例】

10 6 0 6 16 6 24 14 50 41


热腾腾的代码来啦!(σ?∀?)σ..:*☆哎哟不错哦

原文地址:https://www.cnblogs.com/ljy-endl/p/11348970.html

时间: 08-13

线段树(超详细!!!)的相关文章

HDU 1754 I Hate It(线段树之单点更新,区间最值)

I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 70863    Accepted Submission(s): 27424 Problem Description 很多学校流行一种比较的习惯.老师们很喜欢询问,从某某到某某当中,分数最高的是多少. 这让很多学生很反感.不管你喜不喜欢,现在需要你做的是,就是按照老师的

hdu 4973 A simple simulation problem.(线段树)

http://acm.hdu.edu.cn/showproblem.php?pid=4973 有两种操作 D l r 将[l,r]区间翻倍 Q l r询问[l,r]中相同数字出现的最多次数 比赛的时候脑子太乱了,没有想到怎么做.发现每次翻倍序列的长度都在变化,区间对应的数也在变,没有思路. 但是静下心来想一想,思路还是挺清晰的. 无论怎么翻倍,序列中的数都是连续的,范围是1~n.可以拿一个数组来记录每个数出现的次数,当更新或询问区间[l,r]时,可以利用其前缀和找到区间[l,r]对应的数字分别是

HDU5669 Road 分层最短路+线段树建图

分析:(官方题解) 首先考虑暴力,显然可以直接每次O(n^2) ?的连边,最后跑一次分层图最短路就行了. 然后我们考虑优化一下这个连边的过程 ,因为都是区间上的操作,所以能够很明显的想到利用线段树来维护整个图, 连边时候找到对应区间,把线段树的节点之间连边.这样可以大大缩减边的规模,然后再跑分层图最短路就可以了. 但是这样建图,每一次加边都要在O(logn)个线段树节点上加边,虽然跑的非常快,但是复杂度仍然是不科学的. 为了解决边的规模的问题,开两棵线段树,连边时候可以新建一个中间节点,在对应区

HUT 线段树练习 部分题解

F-poj 2886 这题去年月神给我们14级的抓过.然而比较偏数学. 题意大概是n个小朋友围成一圈,每个小朋友手里都有一张卡片,卡片上有个数字a[i]. 从第k个小朋友开始,第k个小朋友出圈,然后让他的左手方向的第a[k]个小朋友出圈.然后这个小朋友又根据规则让另一个小朋友出圈. 第p个出圈的小朋友拿到的糖果数目为p的因子个数,问谁拿到了最多的糖果 可以打反素数表的方式来做(百度即可),但这里介绍另一种方法,就是我们可以直接dfs出小于n的,因子个数最多的数 因为要使因子个数尽量的多,该数应该

hdu 5195 线段树

题目描述:给定一个DAG,求出允许移除最多K条边后的字典序最大的拓扑序列. 思路:线段树,每次找入度不超过K的最大编号的顶点,将此顶点从图中移除,重复操作n次即可得到结果. 吐槽:当时打BC的时候写出了一个直接贪心+拓扑排序的复杂度为O(n)的错误代码(当时还没有意识到是错误代码),交到hdu oj上居然给过了,后来上西方文化的时候和csc得瑟,说那个题我300+ms就给过了,在best solutions里面Rank 1,复杂度还是O(n)的,然后和csc说了我的想法以后才发现这思路TM根本就

SPOJ COT3 Combat on a tree(Trie树、线段树的合并)

题目链接:http://www.spoj.com/problems/COT3/ Alice and Bob are playing a game on a tree of n nodes.Each node is either black or white initially. They take turns to do the following operation:Choose a white node v from the current tree;Color all white node

hdu 4638 Group(莫队算法|离线线段树)

Group Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1323    Accepted Submission(s): 703 Problem Description There are n men ,every man has an ID(1..n).their ID is unique. Whose ID is i and i-

pojHelp with Intervals线段树解法

题:点击打开链接 分析:稍加分析一下交并关系,很好理解.要求掌握线段树区间更新.注意几点:由于是连续的集合,而线段树是节点,所以要将集合扩大两倍以便用点表示.注意输入[0,x)(x是任意大于0的数)即a(左边)为0,并且包含,当处理0到a-1时a-1为-1,会报RE. 此处用到延迟标记col,col=0时将标记的区间更新为0:col为1时将区间更新为1:col为2时将区间翻转.其中col为2时翻转操作1-col表示:当col为0时会翻转为1:当col为1时会翻转为0:当col为-1(不用作处理)

hdu 4893 (多校1007)Wow! Such Sequence!(线段树&amp;二分&amp;思维)

Wow! Such Sequence! Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 352    Accepted Submission(s): 104 Problem Description Recently, Doge got a funny birthday present from his new friend, Prot

南阳理工 题目9:posters(离散化+线段树)

posters 时间限制:1000 ms  |  内存限制:65535 KB 难度:6 描述 The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally deci