線分ツリーの基本的な適用-区間の最上位クエリー

線分の木に影がもうすぐあるような気がします.のまずは一番簡単なことから始めましょう.肝心なのは原理を理解することだ.
区間の最小値を求めます:
タイトル:
2//testcases
 
5 3//n:配列要素個数,m:クエリー回数
78 1 22 12 3//配列を入力し、各数の最大値は10^5を超えない
1 2//lからrまでの最小値のクエリ
3 5
4 4

#include 
#include 
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

using namespace std;
const int maxn = 105000;
int MIN[maxn<<2];
void PushUP(int rt)
{
    MIN[rt] = min(MIN[rt<<1] , MIN[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    if (l == r) {
       // printf("%d  %d  ",l,rt);   
        scanf("%d",&MIN[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}

int query(int L,int R,int l,int r,int rt)
{
    if (L <= l && r <= R) {
        return MIN[rt];
    }
    int m = (l + r) >> 1;
    int ret = 100090;
    if (L <= m) ret = min(ret , query(L , R , lson));
    if (R > m) ret = min(ret , query(L , R , rson));
    return ret;
}

void update(int p,int sc,int l,int r,int rt) {        // ， 
	if (l == r) {
		MIN[rt] = sc;
		return ;
	}
	int m = (l + r) >> 1;
	if (p <= m) update(p , sc , lson);
	else update(p , sc , rson);
	PushUP(rt);
}

int main()
{
    int n , m;
    int casesNum;
    scanf("%d",&casesNum);
    for(int t=1; t<=casesNum; t++) {
        scanf("%d%d",&n,&m);
        build(1 , n , 1);
        printf("Case %d:
",t);
        while (m --) {
            int a , b;
            scanf("%d %d",&a,&b);
            printf("%d
",query(a , b , 1 , n , 1));
        }

    }
    return 0;
}

転載先:https://www.cnblogs.com/MicZ/archive/2012/10/06/2785363.html