题目
给定一组数，要求进行若干次操作，这些操作可以分为两种类型：
（1） CMD 1 beg end value 将数组中下标在[beg, end] 区间内数字都变为value
（2） CMD 2 beg end 求出数组中下标在[beg ,end]区间中的所有数字的和
分析
树状数组在区间查询和单点修改情况下效率较线段树高一些，而无法像线段树一样在O(logN)的时间内完成区间修改。因此使用线段树解决。使用线段树主要的是定义好线段树节点的状态。（如代码中注释所说，状态一定要明确，且容易计算！）
实现
#include<iostream>
#include<string.h>
#include<iostream>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<vector>
using namespace std;
const int inf = 1 << 29;
const int kMax = 100005;
struct Node{
int beg;
int end;
int val;
//若val为非零值，表示当前时刻，节点所代表的区间内所有的值同时被修改为val；
//如果为0，一种情况是该节点代表区间内的值同时被修改为val，
//一种情况是：该区间内的值没有被同时修改为val（可能从没被修改过，或者之前被同时修改过，但是后来又被修改了其中一部分）
int sum; //当前时刻，区间内所有数字的和。这个值就是当前时刻的值，不需要参考value
Node(){
val = sum = 0;
}
};
Node gNodes[4 * kMax];
int weight[kMax];
void BuildTree(int node, int beg, int end){
gNodes[node].beg = beg;
gNodes[node].end = end;
if (beg == end){
gNodes[node].val = gNodes[node].sum = weight[beg]; //初始化
return;
}
int left = 2 * node + 1, right = 2 * node + 2;
int mid = (beg + end) / 2;
BuildTree(left, beg, mid);
BuildTree(right, mid + 1, end);
gNodes[node].sum = gNodes[left].sum + gNodes[right].sum;
}
//从上向下更新
void PushDown(int node){
if (gNodes[node].beg == gNodes[node].end){
//叶子节点处的更新，注意，由于 线段树的节点中的 sum被定义为当前时刻的真实的和。那么，
//当叶子节点被修改为了value时，同时将sum给计算出来
gNodes[node].sum = gNodes[node].val;
return;
}
int left = 2 * node + 1, right = 2 * node + 2;
if (gNodes[node].val){
//注意，由于 线段树的节点中的 sum被定义为当前时刻的真实的和。那么，每当pushdown，子节点的value被修改时，
//也需要同时将 sum给计算出来！
int value = gNodes[node].val;
gNodes[left].val = gNodes[right].val = value;
gNodes[left].sum = (gNodes[left].end - gNodes[left].beg + 1)*value;
gNodes[right].sum = (gNodes[right].end - gNodes[right].beg + 1)*value;
}
gNodes[node].val = 0;
}
//从下向上更新
void PushUp(int node){
if (gNodes[node].beg == gNodes[node].end){
gNodes[node].sum = gNodes[node].val;
return;
}
int left = 2 * node + 1, right = 2 * node + 2;
gNodes[node].sum = gNodes[left].sum + gNodes[right].sum;
}
void Update(int node, int beg, int end, int value){
if (beg == gNodes[node].beg && end == gNodes[node].end){
//对区间进行更新，节点的val 更新为value不用说了。注意由于我们定义的 节点中的sum为当前时刻的真实的和，因此
//需要实时的计算出来
gNodes[node].val = value;
gNodes[node].sum = gNodes[node].val*(gNodes[node].end - gNodes[node].beg + 1);
return;
}
if (beg > end)
return;
//查询区间和线段树节点代表的区间不同，则进行区间分解。 需要先将父节点的信息传递给子节点
PushDown(node);
int left = 2 * node + 1, right = 2 * node + 2;
int mid = (gNodes[node].beg + gNodes[node].end) / 2;
if (mid >= end){
Update(left, beg, end, value);
}
else if(mid < beg){
Update(right, beg, end, value);
}
else{
Update(left, beg, mid, value);
Update(right, mid + 1, end, value);
}
//线段树子节点更新完之后，需要更新父节点的 sum 信息
PushUp(node);
}
int Query(int node, int beg, int end){
if (gNodes[node].beg == beg && gNodes[node].end == end){
return gNodes[node].sum;
}
if (beg > end)
return 0;
PushDown(node);
int left = 2 * node + 1, right = 2 * node + 2;
int mid = (gNodes[node].beg + gNodes[node].end) / 2;
if (mid >= end){
return Query(left, beg, end);
}
else if (mid < beg){
return Query(right, beg, end);
}
else{
int left_sum = Query(left, beg, mid);
int right_sum = Query(right, mid + 1, end);
return left_sum + right_sum;
}
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &weight[i]);
}
BuildTree(0, 0, n - 1);
scanf("%d", &n);
int cmd, beg, end, value;
for (int i = 0; i < n; i++){
scanf("%d", &cmd);
if (cmd == 0){
scanf("%d %d", &beg, &end);
int result = Query(0, beg - 1, end - 1);
printf("%d
", result);
}
else{
scanf("%d %d %d", &beg, &end, &value);
Update(0, beg - 1, end-1, value);
}
}
return 0;
}