精华内容
下载资源
问答
  • 2016-08-18 23:29:26

    链接:点击打开链接

    Input
    第一行一个整数T,表示有T组数据。
    每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
    接下来每行有一条命令,命令有4种形式:
    (1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
    (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
    (3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
    (4)End 表示结束,这条命令在每组数据最后出现;
    每组数据最多有40000条命令
     

    Output
    对第i组数据,首先输出“Case i:”和回车,
    对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
     

    Sample Input
      
    1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
     

    Sample Output
      
    Case 1: 6 33 59

    思路:非常典型的线段树点更新,为什么不能用数组表示每个兵营呢?因为虽然最多只有50000个,但最多进行40000条输出,会超时。

    这个题是求区段总和,所以不需要求出区段最大值,而且更新时加减操作,模板需要稍稍改变一下;

    吐槽:(并没有ac,因为杭电这个题数组卡的太严啦交了好几次都是越界,实在没脾气了......大概改成c可以过?

    (哪天心情平静的时候再战!

    终于知道哪里错了!!!实力懵逼!!!

    代码:

    #include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<cmath>
    #include<algorithm>
    #include<string>
    #include<string.h>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<functional> 
    #include<map>
    using namespace std;
    const int mxn = 50000 + 10;
    
    struct node {
    	int l, r, maxn, sum;//存储最大值与和
    }tree[mxn<<2];
    
    int t, n;
    char str[10];
    int x, y;
    int a[mxn];
    
    void build(int m, int l, int r) {
    	tree[m].l = l;
    	tree[m].r = r;
    	if (l == r) {
    		tree[m].sum = a[l];
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(m << 1, l, mid);
    	build((m << 1) + 1, mid + 1, r);
    	//tree[m].maxn = max(tree[m << 1].maxn, tree[(m << 1) + 1].maxn);
    	tree[m].sum = tree[m << 1].sum + tree[(m << 1) + 1].sum;
    }
    
    void update(int m, int a, int val) {
    	if (tree[m].l == a && tree[m].r == a) {
    		//tree[m].maxn += val;
    		tree[m].sum += val;
    		return;
    	}
    	int mid = (tree[m].l + tree[m].r) >> 1;
    	if (a <= mid)
    		update(m << 1, a, val);
    	else
    		update((m << 1) + 1, a, val);
    	//tree[m].maxn = max(tree[m << 1].maxn, tree[(m << 1) + 1].maxn);
    	tree[m].sum = tree[m << 1].sum + tree[(m << 1) + 1].sum;
    }
    int query_sum(int m, int l, int r) {
    	if (l == tree[m].l && r == tree[m].r)
    		return tree[m].sum;
    		// return tree[m].maxn;
    	int mid = (tree[m].l + tree[m].r) >> 1;
    	if (r <= mid)
    		return query_sum(m << 1, l, r);
    	if (l > mid)
    		return query_sum((m << 1) + 1, l, r);	
    	return query_sum(m << 1, l, mid) + query_sum((m << 1) + 1, mid + 1, r);
    	//return max(query_max(m << 1, l, mid), query_max((m << 1) + 1, mid + 1, r));
    }
    
    int main()
    {
    	int k = 0;
    	scanf("%d", &t);
    	while (t--) {	//居然,,,是这里,,,错了	
    		scanf("%d", &n);		
    		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    		printf("Case %d:\n", ++k);
    		build(1, 1, n);
    		while (scanf("%s", str)) {
    			if (str[0] == 'E')   break;
    			if (str[0] == 'A') {
    				scanf("%d %d", &x, &y);
    				update(1, x, y);
    			}
    			if (str[0] == 'S') {
    				scanf("%d %d", &x, &y);
    				update(1, x, -y);
    			}
    			if (str[0] == 'Q') {
    				scanf("%d %d", &x, &y);
    				printf("%d\n", query_sum(1, x, y));
    			}
    		}
    	}
    	//system("pause");
    	return 0;
    }


    更多相关内容
  • 节点更新线段树

    2013-05-18 11:07:20
    可移植代码,用于单点更新,内有代码移植及运用的详解
  • 线段树区间更新code

    2017-12-22 16:49:22
    线段树区间更新代码线段树区间更新代码线段树区间更新代码线段树区间更新代码
  • 线段树 标签: acm数据结构 2016-08-18 17:26 82人阅读 评论(0) 收藏 举报 分类: 数据结构(9)内容来自石万东学长课件~1.问题 给你一个数的序列A1A2……An。 并且可能多次进行下列两个操作 1、对序列里面的某个数...
     线段树
    标签: acm数据结构
    2016-08-18 17:26 82人阅读 评论(0) 收藏 举报
    分类:
    数据结构(9)
    
    内容来自石万东学长课件~
    
    1.问题
    给你一个数的序列A1A2……An。 并且可能多次进行下列两个操作
    
           1、对序列里面的某个数进行加减
    
           2、询问这个序列里面任意一个连续的子序列AiAi+1……Aj的和是多少。
    希望第2个操作每次能在log(n)时间内完成
    
    2.线段树
    
    注意:
    
    线段树的分解:
    
            如何从[1,9]分解出[2,8]
    
    分解的规则就是:如果有某个节点代表的区间,完全属于待分解区间,则该节点为“终止”节点,不再继续往下分解
    所有“终止”节点所代表的区间都不重叠,且加在一起就恰好等于整个待分解区间
    
    
    线段树的特征(时间复杂度):
    
    1、线段树的深度不超过log2(n)+1(向上取整,n是根节点对应区间的长度)。
    
    2、线段树上,任意一个区间被分解后得到的“终止节点”数目都是log(n)量级。
    线段树能在O(log(n))的时间内完成插入数据,更新数据、查找、统计等工作,提供了理论依据
    
    
    线段树的题目分类:
    可分为以下四大类:
    1、单点更新:最最基础的线段树,只更新叶子节点,然后回溯更新其父亲结点
    2、成段更新:(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候
    
    3、区间合并 这类题目会询问区间中满足条件的连续最长区间,所以回溯的时候需要对左右儿子的区间进行合并(hdu 1540)
    4、扫描线:这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去 最典型的就是矩形面积并,周长并等题(poj 1151)
    
    
    一、点更新:
    
    建树:
    
    
    
        left和reight代表【2,8】的28struct node{  
            int l,r,maxn,sum; //表示最大值和总和  
         }tree[N<<2];  
    
        void build(int m,int l,int r){  
            tree[m].l = l;  
            tree[m].r = r;  
            if(l == r){  
                tree[m].maxn = a[l];  
                tree[m].sum = a[l];  
                return ;  
            }  
            int mid = (l+r)>>1;  
            build(m<<1,l,mid);  
            build((m<<1)+1,mid+1,r);  
            tree[m].maxn = max(tree[m<<1].maxn,tree[(m<<1)+1].maxn);  
            tree[m].sum = tree[m<<1].sum + tree[(m<<1)+1].sum;  
        }  
    
    
    更新:
    
    
    
        void update(int m,int a,int val){  
            if(tree[m].l == a && tree[m].r == a){  
                tree[m].maxn = val;//tree[m].maxn += val;  
                tree[m].sum = val;//tree[m].sum += val;  
                return ;  
            }  
            int mid = (tree[m].l+tree[m].r)>>1;  
            if(a <= mid)  
                update(m<<1,a,val);  
            else  
                update((m<<1)+1,a,val);  
            tree[m].maxn = max(tree[m<<1].maxn,tree[(m<<1)+1].maxn);  
            tree[m].sum = tree[m<<1].sum + tree[(m<<1)+1].sum;  
        }  
    
    
    查询:
    
    
        int query_max(int m,int l,int r){  
            if(l == tree[m].l && r == tree[m].r)  
                return tree[m].maxn;  
                //return tree[m].sum;  
            int mid = (tree[m].l+tree[m].r)>>1;  
            if(r <= mid)  
                return query_max(m<<1,l,r);  
            if(l > mid)  
                return query_max((m<<1)+1,l,r);  
            return max(query_max(m<<1,l,mid), query_max((m<<1)+1,mid+1,r));  
            //return query_sum(m<<1,l,mid) + query_sum((m<<1)+1,mid+1,r);  
        }  
    
        build(1,1,n);  
        update(1,a,b);  
        query(1,a,b);  
    
    
    二、段更新
    
    延迟标记精讲:点击打开链接
    
    
    
        struct node{  
            ll l,r;  
            ll addv,sum;  
        }tree[maxn<<2];  
    
        void maintain(int id)  
        {  
            if(tree[id].l >= tree[id].r)  
                return ;  
            tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;  
        }  
    
        void pushdown(int id)  
        {  
            if(tree[id].l >= tree[id].r)  
                return ;  
            if(tree[id].addv){  
                int tmp = tree[id].addv;  
                tree[id<<1].addv += tmp;  
                tree[id<<1|1].addv += tmp;  
                tree[id<<1].sum += (tree[id<<1].r - tree[id<<1].l + 1)*tmp;  
                tree[id<<1|1].sum += (tree[id<<1|1].r - tree[id<<1|1].l + 1)*tmp;  
                tree[id].addv = 0;  
            }  
        }  
    
        void build(int id,ll l,ll r)  
        {  
            tree[id].l = l;  
            tree[id].r = r;  
            tree[id].addv = 0;  
            tree[id].sum = 0;  
            if(l==r)  
            {  
                tree[id].sum = 0;  
                return ;  
            }  
            ll mid = (l+r)>>1;  
            build(id<<1,l,mid);  
            build(id<<1|1,mid+1,r);  
            maintain(id);  
        }  
    
        void updateAdd(int id,ll l,ll r,ll val)  
        {  
            if(tree[id].l >= l && tree[id].r <= r)  
            {  
                tree[id].addv += val;  
                tree[id].sum += (tree[id].r - tree[id].l+1)*val;  
                return ;  
            }  
            pushdown(id);  
            ll mid = (tree[id].l+tree[id].r)>>1;  
            if(l <= mid)  
                updateAdd(id<<1,l,r,val);  
            if(mid < r)  
                updateAdd(id<<1|1,l,r,val);  
            maintain(id);  
        }  
    
        void query(int id,ll l,ll r)  
        {  
            if(tree[id].l >= l && tree[id].r <= r){  
                anssum += tree[id].sum;  
                return ;  
            }  
            pushdown(id);  
            ll mid = (tree[id].l + tree[id].r)>>1;  
            if(l <= mid)  
                query(id<<1,l,r);  
            if(mid < r)  
                query(id<<1|1,l,r);  
            maintain(id);  
        }  
    展开全文
  • 点更新线段树

    2017-02-02 14:17:50
    线段树是一种强(傻)大(逼)的数据结构,但博主实在是无聊,只好默默的玩一下这种强(傻)大(逼)的数据结构(博主N年前就已经掌握了这种数据结构)。但博主为了共产(工厂)主义事业,终于写下了这个代码(为...

    线段树是一种强(傻)大(逼)的数据结构,但博主实在是无聊,只好默默的玩一下这种强(傻)大(逼)的数据结构(博主N年前就已经掌握了这种数据结构)。但博主为了共产(工厂)主义事业,终于写下了这个代码(为NOIPPJ的水题奋斗)。

    /*************************************************************************
        > File Name: \LJF\数据结构\树\线段树\单点更新模板.cpp
        > Author: ljf_cnyali
        > Mail: ljfcnyali@gmail.com 
        > Last modifiedz: 2017-02-2 11:49
        > Description: This is a large group of God's program information.
     ************************************************************************/
    
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<queue>
    #include<map>
    #include<set>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    #define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
    #define mem(a) memset((a), 0, sizeof(a))
    #define str(a) strlen(a)
    #define lson l, mid, rt << 1
    #define rson mid + 1, r, rt << 1 | 1
    
    const int maxn = 10000;
    
    int n, m;
    
    int Tree[maxn << 2];
    
    void pushup(int rt) {
        Tree[rt] = Tree[rt << 1] + Tree[rt << 1 | 1];   
    }
    
    void Bulid(int l, int r, int rt) {
        if(l == r) {
            Tree[rt] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        Bulid(lson);
        Bulid(rson);
        pushup(rt);
    }
    
    void update(int pos, int val, int l, int r, int rt) {
        if(l == r) {
            Tree[rt] += val;
            return;
        }   
        int mid = (l + r) >> 1;
        if(pos <= mid)
            update(pos, val, lson);
        else
            update(pos, val, rson);
        pushup(rt);
    }
    
    int query(int L, int R, int l, int r, int rt) {
        if(L <= r && r <= R)
            return Tree[rt];
        int mid = (l + r) >> 1;
        int ret = 0;
        if(L <= mid)
            ret += query(L, R, lson);
        if(R > mid)
            ret += query(L, R, rson);
        return ret;
    }
    
    int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    
    
        return 0;
    }
    
    
    展开全文
  • 线段树区间更新

    2019-05-01 15:16:12
    二、从一个例子理解线段树  创建线段树  线段树区间查询  单节点更新  区间更新 三、线段树实战 -------------------------- 一 概述 线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),...

    目录

    概述

    二、从一个例子理解线段树

      创建线段树

      线段树区间查询

      单节点更新

      区间更新

    三、线段树实战

    --------------------------

    一 概述

    线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

    线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。

    二 从一个例子理解线段树

    下面我们从一个经典的例子来了解线段树,问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值,其中数组大小固定,但是数组中的元素的值可以随时更新。

    对这个问题一个简单的解法是:遍历数组区间找到最小值,时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大,而查询操作很频繁的时候,耗时可能会不满足需求。

    另一种解法:使用一个二维数组来保存提前计算好的区间[i,j]内的最小值,那么预处理时间为O(n^2),查询耗时O(1), 但是需要额外的O(n^2)空间,当数据量很大时,这个空间消耗是庞大的,而且当改变了数组中的某一个值时,更新二维数组中的最小值也很麻烦。

    我们可以用线段树来解决这个问题:预处理耗时O(n),查询、更新操作O(logn),需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

    • 叶子节点是原始组数arr中的元素
    • 非叶子节点代表它的所有子孙叶子节点所在区间的最小值

    例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树(背景为白色表示叶子节点,非叶子节点的值是其对应数组区间内的最小值,例如根节点表示数组区间arr[0...5]内的最小值是1):                                                                                                                           本文地址

    由于线段树的父节点区间是平均分割到左右子树,因此线段树是完全二叉树,对于包含n个叶子节点的完全二叉树,它一定有n-1个非叶节点,总共2n-1个节点,因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作:创建线段树、查询、节点更新 是如何运作的呢(以下所有代码都是针对求区间最小值问题)?

    2.1 创建线段树

    对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树,我们也可以用数组来存储,下面的讨论及代码都是数组来存储线段树,节点结构如下(注意到用数组存储时,有效空间为2n-1,实际空间确不止这么多,比如上面的线段树中叶子节点1、3虽然没有左右子树,但是的确占用了数组空间,实际空间是满二叉树的节点数目: 2 * 2 ^{\lceil \log_2{n}  \rceil} - 1, \lceil \log_2{n}  \rceil 是树的高度,但是这个空间复杂度也是O(n)的 )。

    struct SegTreeNode

    {

      int val;

    };

    定义包含n个节点的线段树 SegTreeNode segTree[n],segTree[0]表示根节点。那么对于节点segTree[i],它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+2]。

    我们可以从根节点开始,平分区间,递归的创建线段树,线段树的创建函数如下:

    复制代码
     1 const int MAXNUM = 1000;
     2 struct SegTreeNode
     3 {
     4     int val;
     5 }segTree[MAXNUM];//定义线段树
     6 
     7 /*
     8 功能:构建线段树
     9 root:当前线段树的根节点下标
    10 arr: 用来构造线段树的数组
    11 istart:数组的起始位置
    12 iend:数组的结束位置
    13 */
    14 void build(int root, int arr[], int istart, int iend)
    15 {
    16     if(istart == iend)//叶子节点
    17         segTree[root].val = arr[istart];
    18     else
    19     {
    20         int mid = (istart + iend) / 2;
    21         build(root*2+1, arr, istart, mid);//递归构造左子树
    22         build(root*2+2, arr, mid+1, iend);//递归构造右子树
    23         //根据左右子树根节点的值,更新当前根节点的值
    24         segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    25     }
    26 }
    复制代码

    2.2 查询线段树

    已经构建好了线段树,那么怎样在它上面超找某个区间的最小值呢?查询的思想是选出一些区间,使他们相连后恰好涵盖整个查询区间,因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下,具体见代码解释

    复制代码
     1 /*
     2 功能:线段树的区间查询
     3 root:当前线段树的根节点下标
     4 [nstart, nend]: 当前节点所表示的区间
     5 [qstart, qend]: 此次查询的区间
     6 */
     7 int query(int root, int nstart, int nend, int qstart, int qend)
     8 {
     9     //查询区间和当前节点区间没有交集
    10     if(qstart > nend || qend < nstart)
    11         return INFINITE;
    12     //当前节点区间包含在查询区间内
    13     if(qstart <= nstart && qend >= nend)
    14         return segTree[root].val;
    15     //分别从左右子树查询,返回两者查询结果的较小值
    16     int mid = (nstart + nend) / 2;
    17     return min(query(root*2+1, nstart, mid, qstart, qend),
    18                query(root*2+2, mid + 1, nend, qstart, qend));
    19 
    20 }
    复制代码

    举例说明(对照上面的二叉树):

    1、当我们要查询区间[0,2]的最小值时,从根节点开始,要分别查询左右子树,查询左子树时节点区间[0,2]包含在查询区间[0,2]内,返回当前节点的值1,查询右子树时,节点区间[3,5]和查询区间[0,2]没有交集,返回正无穷INFINITE,查询结果取两子树查询结果的较小值1,因此结果是1.

    2、查询区间[0,3]时,从根节点开始,查询左子树的节点区间[0,2]包含在区间[0,3]内,返回当前节点的值1;查询右子树时,继续递归查询右子树的左右子树,查询到非叶节点4时,又要继续递归查询:叶子节点4的节点区间[3,3]包含在查询区间[0,3]内,返回4,叶子节点9的节点区间[4,4]和[0,3]没有交集,返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4,叶子节点3的节点区间[5,5]和[0,3]没有交集,返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。

    2.3单节点更新

    单节点更新是指只更新线段树的某个叶子节点的值,但是更新叶子节点会对其父节点的值产生影响,因此更新子节点后,要回溯更新其父节点的值。

    复制代码
     1 /*
     2 功能:更新线段树中某个叶子节点的值
     3 root:当前线段树的根节点下标
     4 [nstart, nend]: 当前节点所表示的区间
     5 index: 待更新节点在原始数组arr中的下标
     6 addVal: 更新的值(原来的值加上addVal)
     7 */
     8 void updateOne(int root, int nstart, int nend, int index, int addVal)
     9 {
    10     if(nstart == nend)
    11     {
    12         if(index == nstart)//找到了相应的节点,更新之
    13             segTree[root].val += addVal;
    14         return;
    15     }
    16     int mid = (nstart + nend) / 2;
    17     if(index <= mid)//在左子树中更新
    18         updateOne(root*2+1, nstart, mid, index, addVal);
    19     else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
    20     //根据左右子树的值回溯更新当前节点的值
    21     segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    22 }
    复制代码

    比如我们要更新叶子节点4(addVal = 6),更新后值变为10,那么其父节点的值从4变为9,非叶结点3的值更新后不变,根节点更新后也不变。

    2.4 区间更新

    区间更新是指更新某个区间内的叶子节点的值,因为涉及到的叶子节点不止一个,而叶子节点会影响其相应的非叶父节点,那么回溯需要更新的非叶子节点也会有很多,如果一次性更新完,操作的时间复杂度肯定不是O(lgn),例如当我们要更新区间[0,3]内的叶子节点时,需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念,这也是线段树的精华所在。

    延迟标记:每个节点新增加一个标记,记录这个节点是否进行了某种修改(这种修改操作会影响其子节点),对于任意区间的修改,我们先按照区间查询的方式将其划分成线段树中的节点,然后修改这些节点的信息,并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候,如果我们到了一个节点p,并且决定考虑其子节点,那么我们就要看节点p是否被标记,如果有,就要按照标记修改其子节点的信息,并且给子节点都标上相同的标记,同时消掉节点p的标记。

    因此需要在线段树结构中加入延迟标记域,本文例子中我们加入标记与addMark,表示节点的子孙节点在原来的值的基础上加上addMark的值,同时还需要修改创建函数build 和 查询函数 query,修改的代码用红色字体表示,其中区间更新的函数为update,代码如下:

    复制代码
      1 const int INFINITE = INT_MAX;
      2 const int MAXNUM = 1000;
      3 struct SegTreeNode
      4 {
      5     int val;
      6     int addMark;//延迟标记
      7 }segTree[MAXNUM];//定义线段树
      8 
      9 /*
     10 功能:构建线段树
     11 root:当前线段树的根节点下标
     12 arr: 用来构造线段树的数组
     13 istart:数组的起始位置
     14 iend:数组的结束位置
     15 */
     16 void build(int root, int arr[], int istart, int iend)
     17 {
     18     segTree[root].addMark = 0;//----设置标延迟记域
     19     if(istart == iend)//叶子节点
     20         segTree[root].val = arr[istart];
     21     else
     22     {
     23         int mid = (istart + iend) / 2;
     24         build(root*2+1, arr, istart, mid);//递归构造左子树
     25         build(root*2+2, arr, mid+1, iend);//递归构造右子树
     26         //根据左右子树根节点的值,更新当前根节点的值
     27         segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
     28     }
     29 }
     30 
     31 /*
     32 功能:当前节点的标志域向孩子节点传递
     33 root: 当前线段树的根节点下标
     34 */
     35 void pushDown(int root)
     36 {
     37     if(segTree[root].addMark != 0)
     38     {
     39         //设置左右孩子节点的标志域,因为孩子节点可能被多次延迟标记又没有向下传递
     40         //所以是 “+=”
     41         segTree[root*2+1].addMark += segTree[root].addMark;
     42         segTree[root*2+2].addMark += segTree[root].addMark;
     43         //根据标志域设置孩子节点的值。因为我们是求区间最小值,因此当区间内每个元
     44         //素加上一个值时,区间的最小值也加上这个值
     45         segTree[root*2+1].val += segTree[root].addMark;
     46         segTree[root*2+2].val += segTree[root].addMark;
     47         //传递后,当前节点标记域清空
     48         segTree[root].addMark = 0;
     49     }
     50 }
     51 
     52 /*
     53 功能:线段树的区间查询
     54 root:当前线段树的根节点下标
     55 [nstart, nend]: 当前节点所表示的区间
     56 [qstart, qend]: 此次查询的区间
     57 */
     58 int query(int root, int nstart, int nend, int qstart, int qend)
     59 {
     60     //查询区间和当前节点区间没有交集
     61     if(qstart > nend || qend < nstart)
     62         return INFINITE;
     63     //当前节点区间包含在查询区间内
     64     if(qstart <= nstart && qend >= nend)
     65         return segTree[root].val;
     66     //分别从左右子树查询,返回两者查询结果的较小值
     67     pushDown(root); //----延迟标志域向下传递
     68     int mid = (nstart + nend) / 2;
     69     return min(query(root*2+1, nstart, mid, qstart, qend),
     70                query(root*2+2, mid + 1, nend, qstart, qend));
     71 
     72 }
     73 
     74 /*
     75 功能:更新线段树中某个区间内叶子节点的值
     76 root:当前线段树的根节点下标
     77 [nstart, nend]: 当前节点所表示的区间
     78 [ustart, uend]: 待更新的区间
     79 addVal: 更新的值(原来的值加上addVal)
     80 */
     81 void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
     82 {
     83     //更新区间和当前节点区间没有交集
     84     if(ustart > nend || uend < nstart)
     85         return ;
     86     //当前节点区间包含在更新区间内
     87     if(ustart <= nstart && uend >= nend)
     88     {
     89         segTree[root].addMark += addVal;
     90         segTree[root].val += addVal;
     91         return ;
     92     }
     93     pushDown(root); //延迟标记向下传递
     94     //更新左右孩子节点
     95     int mid = (nstart + nend) / 2;
     96     update(root*2+1, nstart, mid, ustart, uend, addVal);
     97     update(root*2+2, mid+1, nend, ustart, uend, addVal);
     98     //根据左右子树的值回溯更新当前节点的值
     99     segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    100 }
    复制代码

    区间更新举例说明:当我们要对区间[0,2]的叶子节点增加2,利用区间查询的方法从根节点开始找到了非叶子节点[0-2],把它的值设置为1+2 = 3,并且把它的延迟标记设置为2,更新完毕;当我们要查询区间[0,1]内的最小值时,查找到区间[0,2]时,发现它的标记不为0,并且还要向下搜索,因此要把标记向下传递,把节点[0-1]的值设置为2+2 = 4,标记设置为2,节点[2-2]的值设置为1+2 = 3,标记设置为2(其实叶子节点的标志是不起作用的,这里是为了操作的一致性),然后返回查询结果:[0-1]节点的值4;当我们再次更新区间[0,1](增加3)时,查询到节点[0-1],发现它的标记值为2,因此把它的标记值设置为2+3 = 5,节点的值设置为4+3 = 7;

    其实当区间更新的区间左右值相等时([i,i]),就相当于单节点更新,单节点更新只是区间更新的特例。

    三 线段树实战

     求区间的最大值、区间求和等问题都是采用类似上面的延迟标记域。下面会通过acm的一些题目来运用一下线段树。

     

    等待更新......

    参考资料

    GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

    GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

    懂得博客[数据结构之线段树]:http://dongxicheng.org/structure/segment-tree/

    MetaSeed[数据结构专题—线段树]: http://blog.csdn.net/metalseed/article/details/8039326

    NotOnlySuccess[完全版 线段树]: http://www.notonlysuccess.com/index.php/segment-tree-complete/

    转载自:http://www.cnblogs.com/TenosDoIt/p/3453089.html

    展开全文
  • 线段树(Segment Tree)

    2021-01-08 02:11:54
    版权声明:本文为CSDN博主「Alex_McAvoy」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文...线段树是一种二叉搜索树,其存储的是一个区间的信息,每个结点以结构体的形式去存储,每个结构体包含三个元素:
  • // hdu 2795 Billboard 线段树 点更新 // // 首先n最多是200000种,也就是说最多200000行, // 我们的线段树的区间保存的是L到R中最大的叶子节点的值 // 初始情况下都是板子的宽度。这样,每次放一块广告的时候 // ...
  • // hdu 1394 Minimum Inversion Number 线段树 点更新 // // 典型线段树的单点更新 // // 对于求逆序数,刚开始还真的是很年轻啊,裸的按照冒泡排序 // 求出最初始的逆序数,然后按照公式递推,结果就呵呵了 // // ...
  • // hdu 1166 敌兵布阵 线段树 点更新 // // 这道题裸的线段树点更新,直接写就可以了 // // 一直以来想要进线段树的坑,结果一直没有跳进去,今天算是跳进去吧, // 虽然十分简单,十分的水,继续加油 #include ...
  • 在一个区间内,需要同时实现两个操作:更新+查询,如果我们仅仅使用数组来实现,它的时间复杂度时O(n)级别的,相对来说,如果我们使用线段树,便可以获得更好的时间复杂度和更高的执行效率。 例如,我们需要在一...
  • 线段树(区间更新+区间最大)

    千次阅读 2021-03-16 14:15:59
    维护四颗线段树(2,3,5,7)分别统计质数个数,查询每一棵树区间最大值,四棵树中的最大值即为答案。 #include #include #include #include #include #include #include #include #include #include #include #...
  • 【数据结构】数组区间更新-线段树

    千次阅读 多人点赞 2022-02-05 11:38:01
    本期文章的参考代码以及LeetCode699:github 目录 一、线段树的认识以及构造方法 二、build方法 三、add方法 三、update方法 四、query方法 五、如何调用该线段树 一、线段树的认识以及构造方法 线段树:就是为了在...
  • http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1472 #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&...#define maxn ...
  • 线段树(区间更新

    2018-06-06 17:18:39
    void Build(int l, int r, int rt) ///建线段树 { tree[rt].l = l; tree[rt].r = r; tree[rt].sum = 0; tree[rt].lazy = 0; if(l == r) { tree[rt].sum = a[l]; return; } int mid = (l + r) / 2; Build...
  • 线段树的单查询 先判断当前区间[l,r][l,r][l,r]是否与目标区间完全相等 下发标记,请参考 就是玩儿 分解区间 上传标记 线段树的区间修改 请参考 模板 #include <bits/stdc++.h> using namespace std; ...
  • 一、线段树的用处  在对一组连续的数据进行修改或者求和(求最值)操作时,线段树可以通过快速的修改子区间上的值来达成你的目标。     二、线段树是什么  线段树是一种二叉搜索树,它将一个区间划分成一些...
  • 线段树(java)

    千次阅读 2022-04-07 12:37:03
    线段树描述: 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成...代码实现如下:主要实现了线段树的构建,单点更新、区间和、最大值和一些测试用例 import java.util.Scanner; public class Xds { //线段树
  • * 在以treeIndex为根的线段树更新的index的值为e * @param treeIndex 当前位置 * @param l * @param r * @param index * @param e */ //在以trrIndex为根的线段中线段树中更index的值为e ...
  • ①、什么是线段树? 答:线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。它能够实现很多功能,例如快速求区间和、求区间最大值、求区间最小值等。...
  • 数据结构 线段树--权值线段树 详解

    千次阅读 2021-05-29 11:21:24
    线段树是一种用于维护区间信息的高效数据结构,可以在 O(log⁡N)O(\log N)O(logN) 的时间复杂度内实现单修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。 线段树维护的信息必须满足可加...
  • 用Java实现线段树

    2022-01-21 21:29:45
    线段树是为区间更新和区间查询而生的数据结构,旨在快速解决区间问题。​ 一般来说,线段树是不会加节点的,也不支持动态添加节点。线段树也是二叉树的一种,不过它的节点是以一个区间来定义节点的。具有一个单一...
  • [线段树][C++]线段树模板

    千次阅读 2022-04-24 19:00:25
    C++实现基础线段树模板
  • 线段树.pdf

    2016-12-05 19:57:06
    线段树完全版,涉及到线段树的所有用法。 包括单点更新(增减,替换),区间求和,区间最值。 区间求最大值的位置。 成段更新(延迟标记,增减)。 离散化 扫描线
  • poj2481之线段树点更新

    千次阅读 2013-05-28 09:04:32
    每次更新e,更新的目的是使得包含e的区间含有的个数+1 对于比牛[s,e]强壮的牛的个数则只要查询区间[e,MAX]内的的个数 (由于前面更新的牛s当前的牛的s,所以只要前面的牛的e>=当前的牛的e即可,即求[e,MAX]含有...
  • 线段树及例题(含题解)汇总(持续更新) 该来的总要来,寒假没好好学,现在就得为寒假的懒买单(呜呜呜)。看了一天的线段树,虽然看懂还是很容易,毕竟就是一个特殊二叉树,但是实际应用却还是很复杂的,于是开始...
  • 出处:清华大学 张昆玮(zkw) - ppt《统计的力量》 重口味线段树不仅比普通线段树速度快、空间小,而且码量小得多,循环结构思路也很清晰,很适合用来优化Dijkstra和套在树剖以及树套树上。
  • 线段树是一种非常有效降低时间复杂度的数据结构,利用二分原理将区间不断在树结构中放小直至变为。 基础题(我开始学线段树,这是AC的第一道线段树题…) 题目如下: AC代码:(含详细注解,这个真的很详细呀!!!)...
  •  每次折叠可以用线段树暴力维护每个的厚度,因为每次折叠区间都在不断缩小,所以暴力更新均摊下来也不会慢 #include #include #include #include using namespace std; #define maxn ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,132
精华内容 18,052
关键字:

线段树点更新