题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，

跟上一题的成段更新有所不同的是  此处的更新不是直接变成某一个值 而是在原来的基础上加上某一个值 所以 标记的变量也有所改变 是在原来的基础上加上那个值 （一开始 我以为标记变量只是标记用的 具体的加减在sum变量里进行 导致 答案错误） 另外这道题目 数据比较大，超过了int 范围注意到了sum的范围 但是没有注意到标记变量 col 的范围 导致答案错误 #include <iostr

当我们遇到简单的区间问题时，一般会想到树状数组或者线段树。但是当区间信息不符合区间可加可减性时，我们就要另寻他路了。这时我们可以选择用分块来解决问题。 分块要将你要处理的区间划分成长度大致相等的几块。为什么是大致相等呢？因为最后一个剩下的区间长度是难以控制的，剩下来的长度我们就让它自己成为一个区间，大概是这个样子。 对于分块来说，我们要先记录下每个区间的左右极限，以及每个点所在的区间，比如点 1

线段树成段更新操作及Lazy思想（POJ3468解题报告） 标签： treequerybuildn2cstruct 2011-11-03 20:37  5756人阅读  评论(0)  收藏  举报   分类： POJ解题报告（5）   数据结构（21）  版权声明：本文为博主原创文章，未经博主允许不得转载。 就直接那POJ上面的例题来说吧

继续上文 http://128kj.iteye.com/blog/1738772： 在那里用链状结构实现了二叉线段树，下面程序使用一维数组以完全二叉树的方式来存储。 先看一维数组存储线段树到底需要开多大的数组，网上有一个计算程序： Java代码 import java.util.Scanner; /*线段树空间计算程序 Power By:Comzyh*/ class

题目链接：A Simple Problem with Integers 题意：n个数，q次操作，操作分为询问和修改操作，修改是让[a,b]的元素加上c，查询是求[a,b]元素的和 解析：线段树，区间修改，区间查询 #include <algorithm>#include <cstdio>#include <cstring>#include <iostream>using namesp

题目： A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 114345 Accepted: 35470Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN.