hdu1698Just a Hook 树状数组线段树STRMQ

题目大意：有一个区间1~n,初始值每个点的值都是1，现在要对区间的子区间内的点的值做统一的一些修改，每次修改的值为1~3之间，当这些修改完毕之后要求你求1~n之间的所有点的和。
题目连接http://acm.hdu.edu.cn/showproblem.php?pid=1698
解题思路：这其实就是一个入门级别的带区间更新的线段树！前面我已经讲过线段树的创建、单点更新和简单的查询了、所以这里我着重要讲的就是线段树的区间更新问题。
我们知道线段树的没一个节点其实代表的都是一个区间里面的最值，但是在这个问题里面我们表示将不在是这个区间的最值，而是这个区间的统一的值，或者是不统一的值，因此我们在定义节点结构体的时候，里面应该加一个属性叫做value，就本题而言，value的取值范围是1、2、3,0,前面三个属性其实代表的就是节点代表的区间的统一的一个值，而当value=https://www.it610.com/article/0的时候，就意味着这个节点内有多种不同的值，所以当我们求和的时候，就应该进入下一层节点，将这些值不同的区间分别相加!

typedef struct node{ int left; int right; int value; };

首先我们建树，将所有节点的value值赋值为1.

node tree[4*N]; void build(int root,int l,int r){ tree[root].left= l; tree[root].right=r; tree[root].value=https://www.it610.com/article/1; if(l==r) return ; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); return ; }

然后我们要写区间更新的函数了，在区间更新的时候应该怎么样取跟新呢？这里要顺带提一下线段树的精髓，lazy标记。什么是lazy标记？
其实从字面意思理解就是一种懒惰的标记的方法，就是说，每次更新的时候，就没必要将每一个子节点都更新了？为什么可以这样呢？试想一下，如果说我要将区间[1~n]的值全部变为3,然后要你求出区间[1~n]的和，你还有必要将[1,n]下面的子节点的值都一一改变吗？答案肯定是NO！。
再考虑我们要修改区间[1,5]内的所有值为2，那么这应该怎么样修改呢？,我们知道节点[1,10]的左子树和右子树所代表的区间分别是[1,5]，和[6,10]，大家仔细看看左子树[1,5]，这是一个多么亮的亮点啊！！！，对！没错，我们的目的不就是要将左子树[1,5]的value的值变为2吗？那父节点[1,10]和右边的兄弟[6,10]怎么办？对于[6,10]又不用做任何的修改，所以不动它就行了，但是对于父节点[1,10]它的两个子节点区间的值并不相等，怎么办？前面我们已经说过了，当区间没有统一的值的时候令value值为0就可以了，这样当要进行查询的时候就知道该区间内没有统一的值，应该去找子树中有统一值得区间，计算！

void updata(int root,int l,int r,int v){ if(tree[root].value=https://www.it610.com/article/=v) return ; if(tree[root].left==l&&tree[root].right==r){ tree[root].value=v; return ; } if(tree[root].value){ tree[root*2].value=tree[root*2+1].value=tree[root].value; tree[root].value=0; } int mid=(tree[root].left+tree[root].right)/2; if(l>mid) updata(root*2+1,l,r,v); else if(r<=mid){ updata(root*2,l,r,v); } else{ updata(root*2,l,mid,v); updata(root*2+1,mid+1,r,v); } return ; }

最后我们来想一下计算的部分，对于被修改过的线段树，我们应该怎么样求得整个区间的值呢？其实我们可以从根节点开始，从上到下进行如下操作就可以了。一、假设当且节点的value的值大于零，也就意味着这个节点的代表的区间有统一的值value,那么这个区间的和值就等于==区间长度*value
二、节点value的值等于0,那么这个区间的和值就等于==左子树区间和值+右子树区间和.
从上面可以看出这个其实就是一个递归的过程！
【hdu1698Just a Hook】

int getAns(int root,int l,int r){ if(tree[root].value){ return (tree[root].right-tree[root].left+1)*tree[root].value; } int mid=(tree[root].left+tree[root].right)/2; return getAns(root*2,l,mid)+getAns(root*2+1,mid+1,r); }

对于所有的操作讲解完毕了！发个本题代码。

#include #define N 100010 typedef struct node{ int left; int right; int value; }; node tree[4*N]; void build(int root,int l,int r){ tree[root].left= l; tree[root].right=r; tree[root].value=1; if(l==r) return ; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); return ; } void updata(int root,int l,int r,int v){ if(tree[root].value=https://www.it610.com/article/=v) return ; if(tree[root].left==l&&tree[root].right==r){ tree[root].value=v; return ; } if(tree[root].value){ tree[root*2].value=tree[root*2+1].value=tree[root].value; tree[root].value=0; } int mid=(tree[root].left+tree[root].right)/2; if(l>mid) updata(root*2+1,l,r,v); else if(r<=mid){ updata(root*2,l,r,v); } else{ updata(root*2,l,mid,v); updata(root*2+1,mid+1,r,v); } return ; } int getAns(int root,int l,int r){ if(tree[root].value){ return (tree[root].right-tree[root].left+1)*tree[root].value; } int mid=(tree[root].left+tree[root].right)/2; return getAns(root*2,l,mid)+getAns(root*2+1,mid+1,r); } int main(){ int cas=1; int t,n,m; scanf("%d",&t); int a,b,v,ans; while(t--){ scanf("%d",&n); build(1,1,n); scanf("%d",&m); while(m--){ scanf("%d%d%d",&a,&b,&v); updata(1,a,b,v); } ans=getAns(1,1,n); printf("Case %d: The total value of the hook is %d.\n",cas,ans); ++cas; } return 0; }