Sparse Table

稀疏表(離線演算法)
適合RMQ問題,可快速查詢,時間複雜度O(1)
不可用於區間求和問題

  1. 預處理

先把空間劃分為2的冪次,並用DP建表

動態轉移方程:



dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
//代表從i個數起往後數2的j次方個數中的最大值

有了轉移方程接下來就建表






for(int j=1;j<=log2(n);j++){  //檢查2的幾次方有沒有小於最大值取log
    for(int i=0;i+(1<<j)-1<n;i++){  //檢查i再加上2的j次方會不會超過範圍
        dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    }
}
  1. 查詢

把預查詢的範圍[i,j]分成兩個子範圍
子範圍的值=全部的範圍取log

注意:這裡取出來的k是2的幾次方,非子範圍的各數

int k=log2(R-L+1);

有了範圍就可以查表了

int ans=max(dp[L][k],dp[R-(1<<k)+1][k]);

#d539
Sparse Table Code







































#include <stdio.h>
#include <math.h>

int dp[500000][20]={0};

int max(int a,int b){
  if(a>b) return a;
  return b;
}

void swap(int *a,int *b){
  int tmp=*a;
  *a=*b;
  *b=tmp;
}

int main(){
  int n;
  while(EOF!=scanf("%d",&n)){
    for(int i=0;i<n;i++) scanf("%d",&dp[i][0]);
    for(int j=1;j<=log2(n);j++){
      for(int i=0;i+(1<<j)-1<n;i++){
        dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
      }
    }
    int N,x,y;
    scanf("%d",&N);
    while(N--){
      scanf("%d %d",&x,&y);
      x--;y--;
      if(x>y) swap(&x,&y);
      int k=log2(y-x+1);
      printf("%d\n",max(dp[x][k],dp[y-(1<<k)+1][k]));
    }
  }
  
  return 0;
}

Segment Tree code

























































#include <stdio.h>
#include <string.h>

int arr[500000];
int tree[2000000];

int max(int a,int b){
  if(a>b) return a;
  return b;
}

int build_tree(int node,int left,int right){
  if(left==right){
    tree[node]=arr[left];
    return 0;
  }
  int mid=(left+right)/2;
  build_tree(node*2+1,left,mid);
  build_tree(node*2+2,mid+1,right);
  tree[node]=max(tree[node*2+1],tree[node*2+2]);
  return 0;
}

int query_tree(int node,int left,int right,int L,int R){
  if(R<left||L>right) return 0;
  if(right==left||(L<=left&&right<=R)) return tree[node];
  int mid=(right+left)/2;
  int max_left=query_tree(node*2+1,left,mid,L,R);
  int max_right=query_tree(node*2+2,mid+1,right,L,R);
  return max(max_left,max_right);
}

int main(){
  int n;
  while(EOF!=scanf("%d",&n)){
    memset(arr,0,sizeof(arr));
    memset(tree,0,sizeof(tree));
    for(int i=0;i<n;i++){
      scanf("%d",&arr[i]);
    }
    build_tree(0,0,n-1);
    int N;
    scanf("%d",&N);
    while(N--){
      int L,R;
      scanf("%d %d",&L,&R);
      if(max(L,R)==L){
        int tmp=L;
        L=R;
        R=tmp;
      }
      printf("%d\n",query_tree(0,0,n-1,L-1,R-1));
    }
  }
  return 0;
}

C++ sparse table






































#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;

int st[MAXN][20]={0},n;

void sparse_table(){
  for(int j=1;j<=log2(n);j++){
    for(int i=0;i+(1<<j)-1<n;i++){
      st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
  }
}

int query(int l,int r){
  int k=log2(r-l+1);
  return max(st[l][k],st[r-(1 << k)+1][k]);
}

int main(){
  cin.sync_with_stdio(0),cin.tie(0);
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> st[i][0];
  }
  sparse_table();

  int t;
  cin >> t;
  while(t--){
    int l,r;
    cin >> l >> r;
    if(l>r) swap(l,r);
    cout << query(l-1,r-1) << '\n';
  }
  return 0;
}
Select a repo