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;
}