关于zkw式线段树,请参考zkw大牛的ppt--百度文库《统计的力量》,其特点是利用完全二叉树数组存储的特点,自底向上遍历节点,非递归地完成查询和更新,加上位操作的使用,可以提高程序的效率。ps:__int64比long long的效率高很多。
#include <stdio.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 100002
struct tree_node{
int s;
int t;
long long sum; /* A[s]+...+A[t]的部分和 */
long long d; /* A[s]...A[t]的公共增量 */
};
struct tree_node tree[262144];
int A[N];
int M; /* M表示线段树中叶子节点的个数, 对于完全二叉树,M是2的n次幂 */
/* 对[0,M-1]建造线段树,M是2的n次幂,保证了这是一棵完全二叉树 */
void make_tree(int s, int t)
{
int i;
for (i = 2*M-1; i > 0; i--) {
if (i >= M) { /* 叶子节点 */
tree[i].sum = A[i-M];
tree[i].s = tree[i].t = (i-M);
}
else { /* 分支节点 */
tree[i].sum = tree[i<<1].sum + tree[(i<<1)+1].sum;
tree[i].s = tree[i<<1].s;
tree[i].t = tree[(i<<1)+1].t;
}
}
}
/* 区间(s,t)的和等于线段<s,t>的所有匹配线段之和,加上每条匹配线段的累计增量之和 */
long long query(int s, int t)
{
long long sum;
int num_s, num_t; /* 被公共增量影响的元素个数 */
sum = num_s = num_t = 0;
for (s = s+M-1, t = t+M+1; (s^t) != 1;) {
//加上匹配线段的和
if (~s&1) {
sum += tree[s^1].sum;
num_s += (tree[s^1].t-tree[s^1].s+1);
}
if (t&1) {
sum += tree[t^1].sum;
num_t += (tree[t^1].t-tree[t^1].s+1);
}
//加上累计增量
s >>= 1; t >>= 1;
sum += num_s*tree[s].d;
sum += num_t*tree[t].d;
}
//至此,s和t拥有共同的父亲,从它们的父亲开始往上继续加上累计增量,直至根节点
for (s >>= 1;s > 0; s >>= 1) {
sum += (num_s+num_t)*tree[s].d;
}
return sum;
}
/* 除了改变匹配线段的公共增量外,还要改变所有覆盖了匹配线段的线段的sum值 */
void add(int s, int t, int d)
{
int num_s, num_t;
num_s = num_t = 0;
for (s = s+M-1, t = t+M+1; (s^t) != 1;) {
//更新匹配线段的公共增量和sum
if (~s&1) {
tree[s^1].d += d;
tree[s^1].sum += (tree[s^1].t-tree[s^1].s+1)*d;
num_s += (tree[s^1].t-tree[s^1].s+1);
}
if (t&1) {
tree[t^1].d += d;
tree[t^1].sum += (tree[t^1].t-tree[t^1].s+1)*d;
num_t += (tree[t^1].t-tree[t^1].s+1);
}
s >>= 1; t >>= 1;
tree[s].sum += num_s*d;
tree[t].sum += num_t*d;
}
for (s >>= 1; s > 0; s >>= 1) {
tree[s].sum += (num_s+num_t)*d;
}
}
int main()
{
int n, q, i, s, t, value;
long long sum;
char action;
scanf("%d %d", &n, &q);
for (i = 1; i <= n; i++) {
scanf("%d", A+i);
}
/* M表示叶子节点的个数,为了建造完全二叉树,M必须是2的n次幂
* 树的第一个和最后一个叶子节点不能使用,所以叶子
* 节点至少要有n+2个,综上所述,M是大于等于(n+2)且可以
* 表示为2的n次幂的最小整数
*/
for (M = 1; M < (n+2); M <<= 1);
make_tree(0, M-1);
while (q--) {
getchar();
scanf("%c %d %d", &action, &s, &t);
if (action == 'Q') {
sum = query(s, t);
printf("%lld\n", sum);
}
else {
scanf("%d", &value);
if (value != 0) {
add(s, t, value);
}
}
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739064
POJ3468,线段树处理,注意longlongint
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
树状数组解决区间操作_高效 对数组的某个区间进行两种操作: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/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
清华大学 张昆玮 《统计的力量》 POJ上的某题,时限很紧…… 大家都用树状数组,...“下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了。 其实我写的就是线段树。很快,而且不到1k。
线段树、树状数组算法入门 加 poj解题报告 pdf文档
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ题解 个人写法 线段树每个人都不一样
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ2014考研试题表达式·表达式树·表达式求值答案
NULL 博文链接:https://taojianrong.iteye.com/blog/1756785
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...