`
kenby
  • 浏览: 725896 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

poj 3468 线段树朴素递归解法

 
阅读更多

 

一 题意

给定一个数组A,定义Add(s, t, d)的操作为对A[s]...A[t]加d,定义Query(s, t)的操作为查询A[s] + ... + A[t]的值

 

二 算法

在一系列Query操作中,如果每次查询都把A[s]...A[t]加一次,那么要执行加法(t-s+1)次,算法复杂度为O(t-s+1),用线段树,

令线段<x, y>保存A[x]...A[y]的和,对于查询Query(s, t) , 只需在线段树中找到<s,t>对应的若干条线段<s, k>, <k+1, l>,...,<m, t>连接起来刚好组成线段<s, t>,我们把这几条线段称为<s,t>的匹配线段,把它们的和加起来即为所求,加法次数等于匹配

线段的条数,算法复杂度为O(log(t-s+1)),但Add操作就更复杂了,要把所有覆盖<s,t>的线段的和值都更新一遍,算法复杂

度变为O(log(t-s+1))

 

三 实现

每条线段加一个sum属性,用来保存<s,t>的部分和,再加一个d属性,保存A[s]...A[t]的共同增量,Add操作的时候

只需遍历到匹配线段,修改其d属性,不用再往下修改被匹配线段覆盖的孩子节点了。求A[s]+...+A[t]的时候,

把<s,t>的sum和那些覆盖<s,t>的线段的累计增量乘以(t-s+1)加起来即为所求:

A[s]+...+A[t] = <s,t>'s sum + 累计增量*(t-s+1)

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 100001

struct segment_tree_node {
	int s;			/* 线段起始点 */
	int t;			/* 线段终点 */
	long long sum;	/* A[s]+...+A[t]的部分和 */
	long long d;	/* 公共增量 */
};

/* 虽然线段树不一定是完全二叉树,但依然可以用数组表示,只不过浪费一些空间 */
struct segment_tree_node segment_tree[3*N];

int A[N];
int n;

long long sum;
long long sum_d;	/* 累计增量,深度遍历求和的时候用到*/

void make_segment_tree(int r, int s, int t)
{
	int							m, left;
	struct segment_tree_node	*node;

	m = (s+t)>>1;
	node = segment_tree + r;
	node->s = s;
	node->t = t;
	node->d = 0;
	left = r<<1;	/* 左孩子 */
	if (s == t) {
		node->sum = A[s];
		return;
	}
	make_segment_tree(left, s, m);
	make_segment_tree(left+1, m+1, t);
	node->sum = segment_tree[left].sum + segment_tree[left+1].sum;
}

/* 查找A[s]+...+A[t]的和,注意线段的sum只是部分和,
 * 还要加上线段的增量, 如果线段树中不存在线段<s,t>,
 * 则把<s,t>分割为多条线段,比如分割为<s,k>, <k+1,l>, <l+1,t>,
 * 三条子线段,这三条线段都可以在线段树中找到匹配线段, 求出每条
 * 匹配线段的和,加起来就是线段<s,t>的和
 */
void get_sum(int r, int s, int t)
{
	int 						left, m;
	struct segment_tree_node	*node;

	node = segment_tree + r;
	m = (node->s+node->t)>>1;
	left = r<<1;

	/* 一条匹配线段找到,计算它的和,然后加给原始线段的和 */
	if (node->s == s && node->t == t) {		
		sum += (node->sum + (t-s+1)*sum_d);
		return;
	}

	/* 若不是匹配线段,更新增量,继续往下找 */
	sum_d += node->d;
	if (t <= m) {
		get_sum(left, s, t);
	}	
	else if (s > m) {
		get_sum(left+1, s, t);
	}
	else {
		get_sum(left, s, m);
		get_sum(left+1, m+1, t);
	}
	sum_d -= node->d;
}

/* 对A[s]...A[t]之间的每一个元素加d, 体现在线段树中,
 * 所有把匹配线段覆盖掉了的线段,都要更新sum值,而匹配
 * 线段本身要更新d值
 */
void add(int r, int s, int t, long long int d)
{
	int 						m, left;
	struct segment_tree_node	*node;

	node = segment_tree + r;
	m = (node->s+node->t)>>1;
	left = r<<1;
	node->sum += (t-s+1)*d;	/* 覆盖匹配线段的那些线段,
							   都要更新sum值,匹配线段本身也包括在内 */
	if (node->s == s && node->t == t) {
		node->d += d;	/* 只有匹配线段才更新增量值 */
		return;
	}
	if (t <= m) {
		add(left, s, t, d);
	}
	else if (s > m) {
		add(left+1, s, t, d);
	}
	else {
		add(left, s , m, d);
		add(left+1, m+1, t, d);
	}
}

int main() 
{
	int 	q, i, s, t, value;
	char	action;

	scanf("%d %d", &n, &q);
	for (i = 1; i <= n; i++) {
		scanf("%d", A+i);
	}

	make_segment_tree(1, 1, n);

	while (q--) {
		getchar();
		scanf("%c %d %d", &action, &s, &t);
		if (action == 'Q') {
			sum = 0;
			sum_d = 0;
			get_sum(1, s, t);
			printf("%lld\n", sum);
		}
		else {
			scanf("%d", &value);
			add(1, s, t, value);
		}
	}
	return 0;
}
分享到:
评论

相关推荐

    线段树入门学习(二)(兼解POJ3468) JAVA

    在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...

    POJ3468.zip_poj3468

    标题中的"POJ3468.zip_poj3468"显然与编程竞赛相关,POJ(Problemset Online Judge)是北京大学主办的一个在线编程竞赛平台,其中的3468是一个具体的题目编号。这个题目可能涉及到编程挑战,要求参赛者解决特定的...

    POJ3468.zip_ACM

    标题中的"POJ3468.zip_ACM"暗示了这是一个与ACM(国际大学生程序设计竞赛)相关的项目。在ACM比赛中,参赛者需要解决各种算法问题,以提高编程和解决问题的能力。"POJ3468"是这个特定问题的编号,在编程竞赛平台上的...

    线段树练习POJ 3264

    在实际编程中,线段树通常使用递归或迭代的方式来实现。题目中给出的`Main3264.java`文件很可能是实现线段树并解决具体问题的代码。为了更好地理解这个程序,我们需要查看源码,分析其中的类、方法以及它们如何协同...

    POJ 部分题解 解题报告

    6. **POJ 3468 线段树--long long VS int.txt**:线段树是处理区间查询和更新的有效数据结构。这个题目可能关注的是在处理大整数时,线段树的实现细节,尤其是`long long`类型与`int`类型的区别以及其在处理溢出问题...

    POJ 1012 约瑟夫问题的数学解法及分析

    POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

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

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

    poj2823.cpp.tar.gz_线段树

    在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    二维树状数组学习之二:练习POJ 1195

    在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...

    POJ2528-Mayor's posters【区间映射压缩(离散化)+线段树】

    POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========&gt; 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573

    线段树例题(唐文斌).pdf

    ### 线段树例题解析 #### Brackets (SPOJ61, BRCKTS) **题目描述:** 此题要求我们维护一个长度为 \(N\) 的小括号序列 \(A\),并支持两种操作: 1. **Replace(i)**:将第 \(i\) 个位置的括号方向反转。 2. **Check...

    线段树题目

    - **ZOJ 1610** 和 **POJ 2777**:这两道题都是典型的线段覆盖问题,需要利用线段树来解决。基本思路是通过线段树维护每个区间是否被覆盖的状态。对于每个覆盖请求,更新线段树对应区间中的覆盖状态,并统计完全被...

    ACM数据结构之树状数组和线段树

    线段树的构建过程遵循递归策略: 1. **初始化**:首先初始化根节点,对应整个查询区间的范围。 2. **递归构建**:如果当前节点的区间不是单位区间,则继续将其划分为两个子区间,并分别构建左右子树。 3. **终止...

    POJ1013 C解法

    【标题】"POJ1013 C解法"是一个关于解决特定编程竞赛问题的教程,主要关注如何用C语言来实现解决方案。POJ(Problem Solving in Java)是著名的在线编程竞赛平台,它提供了各种算法题目供参赛者挑战,而POJ1013是一...

    poj 2763 housewife Wind

    poj 2763 程序 线段树 LCA 2000MS AC

    poj题目分类

    * 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * 树状树组:例如 poj1195、poj3321。 * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 ...

    POJ2777 个人代码

    POJ题解 个人写法 线段树每个人都不一样

Global site tag (gtag.js) - Google Analytics