一 题意
给定一个数组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,线段树处理,注意longlongint
NULL 博文链接:https://128kj.iteye.com/blog/1739064
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1746750
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
清华大学 张昆玮 《统计的力量》 POJ上的某题,时限很紧…… 大家都用树状数组,...“下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了。 其实我写的就是线段树。很快,而且不到1k。
NULL 博文链接:https://taojianrong.iteye.com/blog/1756785
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...