问题描述
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000
用线段树来解题，一开始的时候结点空间开小了= =
因为N个格子，用线段树的话一共会有2*N-1个结点，所以我不小心就开了2*N-1个结点的空间
结果。。。一半超时。。
修改后发现还是有一个用例超时，上代码：
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX_N = 100005;
#define max(a,b) a>b?a:b
struct NODE{int left; //左子树 int right; //右子树 int totalValue; //总和 int maxValue; //最大值
}node[10 * MAX_N];
int nodeValue[MAX_N];
//建树
void buildTree(int i, int left, int right){node[i].left = left;node[i].right = right;if (left == right){node[i].maxValue = nodeValue[left];node[i].totalValue = nodeValue[left];}else{buildTree(2 * i, left, (left + right) / 2);buildTree(2 * i + 1, (left + right) / 2 + 1, right);node[i].maxValue = node[2 * i].maxValue > node[2 * i + 1].maxValue ? node[2 * i].maxValue : node[2 * i + 1].maxValue;node[i].totalValue = node[2 * i].totalValue + node[2 * i + 1].totalValue;}
}//区间更新
void upDate(int i, int x, int changedX){if (node[i].left == node[i].right){node[i].maxValue = changedX;node[i].totalValue = changedX;}else{if (x <= (node[i].left + node[i].right) / 2)upDate(2 * i, x, changedX);else if (x >= (node[i].left + node[i].right) / 2)upDate(2 * i + 1, x, changedX);node[i].maxValue = node[2 * i].maxValue > node[2 * i + 1].maxValue ? node[2 * i].maxValue : node[2 * i + 1].maxValue;node[i].totalValue = node[2 * i].totalValue + node[2 * i + 1].totalValue;}
}//查找区间最大值
//i表示node[i]结点，left,right表示查找范围
int findMax(int i, int left, int right){int maxValue = -1;if (node[i].left == left && node[i].right == right){ //完全重合 maxValue = max(maxValue, node[i].maxValue);return maxValue;}if (left <= node[2 * i].right){ //范围跟node[i]的左子树有交集 if (right <= node[2 * i].right){maxValue = max(maxValue, findMax(2 * i, left, right));}else{maxValue = max(maxValue, findMax(2 * i, left, node[2 * i].right));}}if (right >= node[2 * i + 1].left){ //范围跟node[i]的右子树有交集 if (left >= node[2 * i + 1].left){ //被右子树完全包含 maxValue = max(maxValue, findMax(2 * i + 1, left, right));}else{maxValue = max(maxValue, findMax(2 * i + 1, node[2 * i + 1].left, right));}}return maxValue;
}//查找区间数值之和
int findTotal(int i, int left, int right){int total = 0;if (node[i].left == left && node[i].right == right){total = node[i].totalValue;return total;}if (left <= node[2 * i].right){if (right <= node[2 * i].right){total = findTotal(2 * i, left, right);}else{total += findTotal(2 * i, left, node[2 * i].right);}}if (right >= node[2 * i + 1].left){if (left >= node[2 * i + 1].left){total = findTotal(2 * i + 1, left, right);}else{total += findTotal(2 * i + 1, node[2 * i + 1].left, right);}}return total;
}
int main(){int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &nodeValue[i]);buildTree(1, 1, n);for (int j = 1; j <= m; j++){int workIndex, x, y;scanf("%d%d%d", &workIndex, &x, &y);switch (workIndex){case 1:upDate(1, x, y);break;case 2:printf("%d\n", findTotal(1, x, y));break;case 3:printf("%d\n", findMax(1, x, y));break;}}
然后我修改了一下，不要在每一个查找区间数值方法里面比较最大值和总和，而是在left == right的时候才比较最大值和总和。
AC代码：
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX_N = 100005;
#define max(a,b) a>b?a:b
struct NODE{int left; //左子树 int right; //右子树 int totalValue; //总和 int maxValue; //最大值
}node[10 * MAX_N];
int nodeValue[MAX_N];int maxValue = -1;
int totalValue = 0;
//建树
void buildTree(int i, int left, int right){node[i].left = left;node[i].right = right;if (left == right){node[i].maxValue = nodeValue[left];node[i].totalValue = nodeValue[left];}else{buildTree(2 * i, left, (left + right) / 2);buildTree(2 * i + 1, (left + right) / 2 + 1, right);node[i].maxValue = node[2 * i].maxValue > node[2 * i + 1].maxValue ? node[2 * i].maxValue : node[2 * i + 1].maxValue;node[i].totalValue = node[2 * i].totalValue + node[2 * i + 1].totalValue;}
}//区间更新
void upDate(int i, int x, int changedX){if (node[i].left == node[i].right){node[i].maxValue = changedX;node[i].totalValue = changedX;}else{if (x <= (node[i].left + node[i].right) / 2)upDate(2 * i, x, changedX);else if (x >= (node[i].left + node[i].right) / 2)upDate(2 * i + 1, x, changedX);node[i].maxValue = node[2 * i].maxValue > node[2 * i + 1].maxValue ? node[2 * i].maxValue : node[2 * i + 1].maxValue;node[i].totalValue = node[2 * i].totalValue + node[2 * i + 1].totalValue;}
}//查找区间最大值
//i表示node[i]结点，left,right表示查找范围
void findMax(int i, int left, int right){if (node[i].left == left && node[i].right == right){ //完全重合 maxValue = max(maxValue, node[i].maxValue);return;}if (left <= node[2 * i].right){ //范围跟node[i]的左子树有交集 if (right <= node[2 * i].right){findMax(2 * i, left, right);}else{findMax(2 * i, left, node[2 * i].right);}}if (right >= node[2 * i + 1].left){ //范围跟node[i]的右子树有交集 if (left >= node[2 * i + 1].left){ //被右子树完全包含 findMax(2 * i + 1, left, right);}else{maxValue, findMax(2 * i + 1, node[2 * i + 1].left, right);}}
}//查找区间数值之和
void findTotal(int i, int left, int right){if (node[i].left == left && node[i].right == right){totalValue += node[i].totalValue;return;}if (left <= node[2 * i].right){if (right <= node[2 * i].right){findTotal(2 * i, left, right);}else{findTotal(2 * i, left, node[2 * i].right);}}if (right >= node[2 * i + 1].left){if (left >= node[2 * i + 1].left){findTotal(2 * i + 1, left, right);}else{findTotal(2 * i + 1, node[2 * i + 1].left, right);}}
}
int main(){int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &nodeValue[i]);buildTree(1, 1, n);for (int j = 1; j <= m; j++){int workIndex, x, y;scanf("%d%d%d", &workIndex, &x, &y);switch (workIndex){case 1:upDate(1, x, y);break;case 2:findTotal(1, x, y);printf("%d\n", totalValue);totalValue = 0;break;case 3:findMax(1, x, y);printf("%d\n", maxValue);maxValue = -1;break;}}/*for(int j = 1;j<=2*n-1;j++){cout<<"left: "<<node[j].left<<endl;cout<<"right: "<<node[j].right<<endl;cout<<"maxValue: "<<node[j].maxValue<<endl;cout<<"totalValue: "<<node[j].totalValue<<endl;}*//*cout<<"1 到 4号格子最大值： "<<findMax(1,1,4)<<endl;cout<<"1 到 2号格子最大值： "<<findMax(1,1,2)<<endl;cout<<"1 到 3号格子最大值： "<<findMax(1,1,3)<<endl;cout<<"2 到 4号格子最大值： "<<findMax(1,2,4)<<endl;cout<<"2 到 3号格子最大值： "<<findMax(1,2,3)<<endl;cout<<"3 到 4号格子最大值： "<<findMax(1,3,4)<<endl;cout<<"1 到 4号格子权值和： "<<findTotal(1,1,4)<<endl;cout<<"1 到 2号格子权值和： "<<findTotal(1,1,2)<<endl;cout<<"1 到 3号格子权值和： "<<findTotal(1,1,3)<<endl;cout<<"2 到 4号格子权值和： "<<findTotal(1,2,4)<<endl;cout<<"2 到 3号格子权值和： "<<findTotal(1,2,3)<<endl;cout<<"3 到 4号格子权值和： "<<findTotal(1,3,4)<<endl;*/
}