`

【线段树 成段更新 lazy标记】LOJ 1164

阅读更多

KIDx的解题报告

 

题目链接:http://lightoj.com/volume_showproblem.php?problem=1164

 

题意:区间内初始时全部为0

命令1:0 x y v; 从x到y全部+v

命令2:1 x y; 输出x到y的值的总和

典型lazy的应用

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define LL long long
#define Max 26

struct Node{
	int l, r;			//sum是l到r的总和
	LL v, sum;			//v积累要加的数,需要往下时才更新儿子:lazy标记
}N[M<<2];

void create (int u, int a, int b)
{
	N[u].l = a, N[u].r = b, N[u].v = N[u].sum = 0;
	if (a == b) return ;
	int mid = (a + b) >> 1, lc = u+u, rc = lc+1;
	create (lc, a, mid);
	create (rc, mid+1, b);
}

void update (int u, int a, int b, LL c)
{
	if (a <= N[u].l && b >= N[u].r)
	{
		N[u].v += c;
		N[u].sum += c * (N[u].r-N[u].l+1);		//注意积累是用+=
		return ;
	}
	int lc = u+u, rc = lc+1;
	if (N[u].v > 0)			//lazy一下,需要访问我儿子,我才去更新
	{
		N[lc].v += N[u].v;
		N[lc].sum += N[u].v * (N[lc].r-N[lc].l+1);
		N[rc].v += N[u].v;
		N[rc].sum += N[u].v * (N[rc].r-N[rc].l+1);
		N[u].v = 0;
	}
	if (a <= N[lc].r)
		update (lc, a, b, c);
	if (b >= N[rc].l)
		update (rc, a, b, c);
	N[u].sum = N[lc].sum + N[rc].sum;
}

LL find (int u, int a, int b) //和比较大,要用long long
{
	if (a <= N[u].l && b >= N[u].r)
		return N[u].sum;
	LL m1 = 0, m2 = 0;
	int lc = u+u, rc = lc+1;
	if (N[u].v > 0)			//同理lazy一下
	{
		N[lc].v += N[u].v;
		N[lc].sum += N[u].v * (N[lc].r-N[lc].l+1);
		N[rc].v += N[u].v;
		N[rc].sum += N[u].v * (N[rc].r-N[rc].l+1);
		N[u].v = 0;
	}
	if (a <= N[lc].r)
		m1 = find (lc, a, b);
	if (b >= N[rc].l)
		m2 = find (rc, a, b);
	return m1+m2;
}

int main()
{
	LL c;
	int t, cc = 1, n, q, k, a, b;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%d", &n, &q);
		create (1, 1, n);
		printf ("Case %d:\n", cc++);
		while (q--)
		{
			scanf ("%d%d%d", &k, &a, &b);
			a++, b++;
			if (k) printf ("%lld\n", find (1, a, b));
			else scanf ("%lld", &c), update (1, a, b, c);
		}
	}
    return 0;
}

 

1
2
分享到:
评论

相关推荐

    点节点更新线段树

    其中,线段树(Segment Tree)是一种高效的数据结构,常被用于处理区间查询或更新的问题。在本篇文章中,我们将深入探讨“点节点更新线段树”的概念、原理以及实现细节,尤其关注单点更新操作。 ### 点节点更新线段...

    线段树完整版

    1. **懒惰标记** (`lazy tag`): 在进行区间更新时,可以在节点上打标记,表示这一整段区间都还没有真正被更新,这样在下一次访问时再进行延迟更新,可以显著减少不必要的更新操作。 2. **区间加法更新** (`range ...

    线段树.pdf

    在更新这类操作时,我们可以使用延迟传播(Lazy Propagation)技术,即标记待更新的区间,在真正需要该区间信息的时候再进行更新。这种方法可以大大减少不必要的操作,提高效率。 离散化是处理大规模数据时的一个...

    线段树入门学习(三)懒操作(兼解POJ1823) JAVA

    在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...

    ZKW线段树源码-pascal

    它的特点在于实现简单,且在更新区间时不需要像传统线段树那样逐层上推标记(lazy propagation),而是通过即时下传标记的方式实现快速的区间更新。 3. ZKW线段树的实现原理 在ZKW线段树的实现中,主要涉及以下几个...

    线段树函数

    线段树可以进一步优化,例如引入懒惰标记(lazy propagation)以减少不必要的更新。当一个区间更新涉及到大量节点时,我们可以暂时不对所有节点进行实际更新,而是仅在需要查询的节点处应用更新。这种方法可以避免...

    完全版线段树

    线段树的优化还包括懒惰标记(Lazy Propagation)技术,用于处理连续的区间更新,避免不必要的递归调用。此外,线段树还可以与其他数据结构结合,如splay树,以实现更快的查询和更新效率。 总的来说,线段树是一种...

    ZKW线段树模板类

    线段树的基本思想是将一维数组划分成若干个子区间,每个子区间对应线段树的一个节点。线段树的每个节点存储对应区间的信息,例如区间和或区间最大值。通过递归地对子节点进行合并,可以快速查询和更新任意区间的值。...

    线段树 经典范例~~~~

    在实现线段树时,我们通常使用lazy propagation(惰性更新)来优化性能。这是因为对于某些区间更新操作,如果不采用惰性更新,可能会导致不必要的递归,增加时间复杂度。惰性更新允许我们在必要时才真正执行更新,...

    线段树中文教程【信息技术竞赛】

    线段树,作为数据结构的一种,广泛应用于计算机科学与编程竞赛中,特别是在处理区间查询和更新问题时展现出高效性。本文旨在深入解析线段树的基本概念、构建原理、关键属性及其实现技巧,同时通过具体实例阐述其在...

    线段树及其应用(刘汝佳)

    线段树是一种高效的数据结构,主要用于处理动态统计问题,即在数据集上进行频繁的查询和更新操作。刘汝佳的讲解被认为是最优秀的资源之一,本文将深入探讨线段树的定义、性质、基本算法以及在不同问题中的应用。 ...

    线段树介绍

    2. 嵌套区间:线段树可以通过额外的数据结构来支持嵌套区间查询和更新,例如懒惰标记(lazy propagation)。当对一个区间进行更新时,如果这个区间跨越了多个子节点,可以在父节点上设置一个“懒惰”标记,等到下次...

    线段树模版(比较基本的线段树以及例题模板)

    关于一些典型的线段树的例题,大家可以看一看,给一个评价,这些内容,后续我也会在博客上慢慢更新。希望大家多多的支持作者,谢谢! 这篇内容主要包含了一些我写的线段树的代码,可以帮助大家更好的理解线段树建树...

    线段树(单点查询+区间求和)无lazy标记

    在“线段树(单点查询+区间求和)无lazy标记”这个题目中,主要涉及到线段树的基本操作,包括如何构建线段树、单点修改以及区间求和。 1. **线段树的构建**: - `build`函数是线段树的初始化过程。它从根节点开始...

    第3章 线段树 测试数据.rar

    当一个区间需要更新时,不是立即更新所有涉及的节点,而是将更新标记存储在父节点上,只有在查询或更新时才真正传播到子节点。 4. **应用实例** 在信息学奥赛中,线段树常用于解决如下问题: - 动态维护一段区间...

    线段树(总共有3个文件,doc)

    对于懒惰传播的线段树,还需要在适当的时候更新被标记的节点,确保数据的准确性。 线段树的应用广泛,包括但不限于以下场景: 1. 动态统计:例如,求一个数组在某一范围内元素的和、最大值或最小值。 2. 范围更新:...

    线段树(acm的资料)

    林涛的文档可能涵盖了线段树的基础概念、构建过程、基本操作(如查询和更新)、以及一些高级技巧,如lazy propagation(懒惰标记)来优化区间更新。薛矛的资料可能不仅限于线段树,也可能涉及了树状数组,这是另一种...

    线段树(一)——概念和应用

    在“Sam's理解延迟标记_扫描线.pptx”这个文件中,可能会详细讲解如何利用延迟标记(Lazy Propagation)优化线段树。延迟标记是处理区间更新的一个技巧,它将未处理的更新信息存储在非叶子节点上,只有在访问到该...

    数据结构【b】线段树及其应用-毕业论文.doc

    4. **优化**:为了进一步提高效率,线段树常常与懒惰标记或线段合并等优化策略结合,延迟一些更新操作直到真正需要查询时才执行。 在设计线段树的抽象数据类型(ADT)时,通常包括以下几个基本函数: - `init_tree(n)...

    线段树汇总

    - **懒惰标记(Lazy Propagation)**:当区间更新较大时,为了减少不必要的更新操作,可以在节点上设置“懒惰标记”,等到真正需要查询或更新子节点时再传播下去。 - **线段树的压缩**:通过减少非叶子节点的数量...

Global site tag (gtag.js) - Google Analytics