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;
}
分享到:
相关推荐
其中,线段树(Segment Tree)是一种高效的数据结构,常被用于处理区间查询或更新的问题。在本篇文章中,我们将深入探讨“点节点更新线段树”的概念、原理以及实现细节,尤其关注单点更新操作。 ### 点节点更新线段...
1. **懒惰标记** (`lazy tag`): 在进行区间更新时,可以在节点上打标记,表示这一整段区间都还没有真正被更新,这样在下一次访问时再进行延迟更新,可以显著减少不必要的更新操作。 2. **区间加法更新** (`range ...
在更新这类操作时,我们可以使用延迟传播(Lazy Propagation)技术,即标记待更新的区间,在真正需要该区间信息的时候再进行更新。这种方法可以大大减少不必要的操作,提高效率。 离散化是处理大规模数据时的一个...
在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...
它的特点在于实现简单,且在更新区间时不需要像传统线段树那样逐层上推标记(lazy propagation),而是通过即时下传标记的方式实现快速的区间更新。 3. ZKW线段树的实现原理 在ZKW线段树的实现中,主要涉及以下几个...
线段树可以进一步优化,例如引入懒惰标记(lazy propagation)以减少不必要的更新。当一个区间更新涉及到大量节点时,我们可以暂时不对所有节点进行实际更新,而是仅在需要查询的节点处应用更新。这种方法可以避免...
当一个区间需要更新时,不是立即更新所有涉及的节点,而是将更新标记存储在父节点上,只有在查询或更新时才真正传播到子节点。 4. **应用实例** 在信息学奥赛中,线段树常用于解决如下问题: - 动态维护一段区间...
线段树的优化还包括懒惰标记(Lazy Propagation)技术,用于处理连续的区间更新,避免不必要的递归调用。此外,线段树还可以与其他数据结构结合,如splay树,以实现更快的查询和更新效率。 总的来说,线段树是一种...
线段树的基本思想是将一维数组划分成若干个子区间,每个子区间对应线段树的一个节点。线段树的每个节点存储对应区间的信息,例如区间和或区间最大值。通过递归地对子节点进行合并,可以快速查询和更新任意区间的值。...
在实现线段树时,我们通常使用lazy propagation(惰性更新)来优化性能。这是因为对于某些区间更新操作,如果不采用惰性更新,可能会导致不必要的递归,增加时间复杂度。惰性更新允许我们在必要时才真正执行更新,...
线段树,作为数据结构的一种,广泛应用于计算机科学与编程竞赛中,特别是在处理区间查询和更新问题时展现出高效性。本文旨在深入解析线段树的基本概念、构建原理、关键属性及其实现技巧,同时通过具体实例阐述其在...
线段树是一种高效的数据结构,主要用于处理动态统计问题,即在数据集上进行频繁的查询和更新操作。刘汝佳的讲解被认为是最优秀的资源之一,本文将深入探讨线段树的定义、性质、基本算法以及在不同问题中的应用。 ...
2. 嵌套区间:线段树可以通过额外的数据结构来支持嵌套区间查询和更新,例如懒惰标记(lazy propagation)。当对一个区间进行更新时,如果这个区间跨越了多个子节点,可以在父节点上设置一个“懒惰”标记,等到下次...
关于一些典型的线段树的例题,大家可以看一看,给一个评价,这些内容,后续我也会在博客上慢慢更新。希望大家多多的支持作者,谢谢! 这篇内容主要包含了一些我写的线段树的代码,可以帮助大家更好的理解线段树建树...
在“线段树(单点查询+区间求和)无lazy标记”这个题目中,主要涉及到线段树的基本操作,包括如何构建线段树、单点修改以及区间求和。 1. **线段树的构建**: - `build`函数是线段树的初始化过程。它从根节点开始...
对于懒惰传播的线段树,还需要在适当的时候更新被标记的节点,确保数据的准确性。 线段树的应用广泛,包括但不限于以下场景: 1. 动态统计:例如,求一个数组在某一范围内元素的和、最大值或最小值。 2. 范围更新:...
林涛的文档可能涵盖了线段树的基础概念、构建过程、基本操作(如查询和更新)、以及一些高级技巧,如lazy propagation(懒惰标记)来优化区间更新。薛矛的资料可能不仅限于线段树,也可能涉及了树状数组,这是另一种...
在“Sam's理解延迟标记_扫描线.pptx”这个文件中,可能会详细讲解如何利用延迟标记(Lazy Propagation)优化线段树。延迟标记是处理区间更新的一个技巧,它将未处理的更新信息存储在非叶子节点上,只有在访问到该...
4. **优化**:为了进一步提高效率,线段树常常与懒惰标记或线段合并等优化策略结合,延迟一些更新操作直到真正需要查询时才执行。 在设计线段树的抽象数据类型(ADT)时,通常包括以下几个基本函数: - `init_tree(n)...
- **懒惰标记(Lazy Propagation)**:当区间更新较大时,为了减少不必要的更新操作,可以在节点上设置“懒惰标记”,等到真正需要查询或更新子节点时再传播下去。 - **线段树的压缩**:通过减少非叶子节点的数量...