###### tags: `經典問題`

# RMQ 問題
## 問題敘述
對於一個長度為 $n$ 的 array，可以實行以下兩種操作。
* $update(x, y)$:
將 array 的第 $x$ 個元素值更新成 $y$。
* $query(l, r)$:
詢問 array 在 $[l, r]$ 這個範圍內的最大值或最小值是多少。

## Segment Tree
線段樹應該是拿來做 RMQ 問題的常用手段了，build 的時間複雜度 $O(n*logn)$，update 與 query 的時間複雜度都是 $O(log(n))$。

要注意線段樹需要 $4n$ 的空間來儲存。

vector<int> tree;
// l, r, idx是線段樹的內部變數
int build(int l, int r, int idx, vector<int> &arr){ // 沒有測試過，但大概的code應該是長這樣
    if(l == r)
        return tree[idx] = arr[l];
    int mid = (l+r)/2;
    int l_result = build(l, mid, idx*2+1, arr);
    int r_result = build(mid+1, r, idx*2+2, arr);
    return tree[idx] = max(l_result, r_result);
}
int update(int l, int r, int idx, int x, int y){ // 將arr[x]改成y
    if(l == r)
        return tree[idx] = y;

    int mid = (l+r)/2;
    if(x<=mid)
        return tree[idx] = max(update(l, mid, idx*2+1, x, y), tree[idx*2+2]);
    else return tree[idx] = max(tree[idx*2+1], update(mid+1, r, idx*2+2, x, y));
}
int query(int l, int r, int L, int R, int idx){ // 找[L, R]中的最大值
    if(L == l && R == r)
        return tree[idx];
    int mid = (l+r)/2;

    if(R<=mid)
        return query(l, mid, L, R, idx*2+1);
    else if(L>mid)
        return query(mid+1, r, L, R, idx*2+2);
    else {
        return max(query(l, mid, L, mid, idx*2+1), query(mid+1, r, mid+1, R, idx*2+2));
    }
}

## Binary Indexed Tree (Fenwick Tree)
根據[這篇](https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-binary-indexed-tree)提到的想法，如果要用 BIT 解決 RMQ 問題，那 update 值的時候，如果要做最大值，那值就只能被改大，做最小值，那值就只能被改小。

這個方法 update 與 query 的時間複雜度應該都是 $O(log(n))$。

要注意 BIT 需要 $n$ 的空間來儲存。

vector<int> BIT, arr; // 1-indexed
// 只能將值改大，不可改小
void update(int idx, int val){ // update arr[idx] = val
    arr[idx] = val;
    for(int i=idx;i<BIT.size();i+=i&-i)
        BIT[i] = max(BIT[i], val);
}
int query(int l, int r){ // query [l, r] 之間的最大值
    int ans = -1;
    for(int i=r;i>=l;){
        if(i - (i&-i) < l){
            ans = max(ans, arr[i]);
            i--;
        }
        else {
            ans = max(ans, BIT[i]);
            i-=i&-i;
        }
    }
    return ans;
}