超初心者が競プロに挑む

初心者からの競プロ練習記録

セグメント木でなぜかすごい詰まったところ

セグメント木で凄まじく詰まったためメモをしておく
下記のコードで、呼び出しの時、calcMin(a,b,0,0,n)ではなくcalcMin(a,b,0,0,N)でなければならない。要するに、セグメント木の実際に使う範囲を指定するのではなく、実際のセグメントのサイズで呼び出さないと正しい結果はでないです。

class SegmentTree {
public:
  long long Storage[MAX_L*2+10];
  int N;
public:
  void init(int n) {
    N=1;
    while(N<n) N*=2;

    for(int i=0;i<N*2;++i) {
      Storage[i]=INF;
    }

    updateLeaf(0, 0);
  }

  void updateLeaf(int i, int value) {
    i += N-1;
    Storage[i]=value;
    while(i>0) {
      i = (i-1) / 2;
      Storage[i] = min(Storage[i*2+1], Storage[i*2+2]);
    }
  }

  long long int getLeaf(int i) {
    i += N -1;
    return Storage[i];
  }

  long long calcMin(int a,int b,int k,int l, int r) {
    if(b<=l || a>=r) return INF;
    if(a<=l && b>=r) {
      return Storage[k];
    } else {
      long long tl = calcMin(a,b,k*2+1,l,(l+r)/2);
      long long tr = calcMin(a,b,k*2+2,(l+r)/2,r);
      return min(tl,tr);
    }
  }
};