# hiho1077 : RMQ问题再临-线段树

hihoCoder
http://hihocoder.com/problemset/problem/1077

include <iostream>include <stdlib.h>using namespace std;

struct node
{
node *father;
node *leftchild;
node *rightchild;
int leftbound;
int rightbound;
int minvalue;
node(){ father = leftchild = rightchild = NULL; leftbound = rightbound = 0; minvalue = 10000; }
};

int mymin(int a, int b)
{
return (a < b ? a : b);
}
int myquery(node *curnode, int left, int right)
{
if (left == curnode->leftbound && right == curnode->rightbound)
{
return curnode->minvalue;
}
int mid = (curnode->leftbound + curnode->rightbound) / 2;
if (right <= mid)
{
return myquery(curnode->leftchild, left, right);
}
if (left > mid)
{
return myquery(curnode->rightchild, left, right);
}
return mymin(myquery(curnode->leftchild, left, mid), myquery(curnode->rightchild, mid + 1, right));
}
node *leaves;
node* buildtree(int *weight,int leftbound,int rightbound)
{
node *tempnode = new node;
if (leftbound == rightbound)
{

tempnode->leftbound = leftbound;
tempnode->rightbound = rightbound;
tempnode->minvalue = weight[leftbound];
leaves[leftbound] = tempnode;
}
else
{
//node *tempnode = new node;
tempnode->leftbound = leftbound;
tempnode->rightbound = rightbound;
tempnode->leftchild = buildtree(weight, leftbound, (leftbound + rightbound) / 2);
tempnode->rightchild = buildtree(weight, (leftbound + rightbound) / 2 + 1, rightbound);
tempnode->leftchild->father = tempnode;
tempnode->rightchild->father = tempnode;
tempnode->minvalue = mymin(tempnode->leftchild->minvalue, tempnode->rightchild->minvalue);
}
return tempnode;
}
void change(node *curnode, int new_weight)
{
if (curnode == NULL)
return;
if (curnode->minvalue > new_weight)
{
curnode->minvalue = new_weight;
change(curnode->father, new_weight);
}
}
int main()
{
int n;
scanf("%d", &n);
//cin >> n;
int *weight = new int[n + 1];
for (int i = 1; i <= n; i++)
scanf("%d", &weight[i]);
//cin >> weight[i];
node *head = buildtree(weight, 1, n);
head->father = NULL;
delete[] weight;
int q;
scanf("%d", &q);
//cin >> q;
for (int k = 0; k < q; k++)
{
int op;
scanf("%d", &op);
//cin >> op;
if (op == 0)//query
{
int l, r;
scanf("%d %d", &l, &r);
//cin >> l >> r;
int ans = myquery(head, l, r);
printf("%d\n", ans);
//cout << ans << endl;
}
else if (op == 1)//change
{
int position, new_weight;
scanf("%d %d", &position, &new_weight);
//cin >> position >> new_weight;
leaves[position]->minvalue = new_weight;
change(leaves[position]->father, new_weight);
}
}
return 0;
}


change的时候不要比较所给的newWeight是否小于当前值，直接替换为newWeight.

• APP下载 七月在线APP
• 微信公众号 扫码免费领课
• 返回顶部