樹状配列は区間の極値を求めます
8520 ワード
このアルゴリズムは、単一の変更と区間クエリの最小値のみをサポートします.メンテナンスやクエリーのたびに時間の複雑さはO((logn)^2)ですが、これは満杯の時間の複雑さです.
区間の最大値を維持してクエリーすると仮定します(最小値はmaxをminに変更すればいいです)
このアルゴリズムは、ツリー配列のメンテナンスとクエリー区間の和の方法と似ています.
一、配列の意味
1、メンテナンスとクエリー区間和のアルゴリズムにおいて、h[x]に格納されているのは[x,x-lowbit(x)+1]の各数の和であり、
2、区間最値を求めるアルゴリズムでは、h[x]は[x,x-lowbit(x)+1]の各数の最大値を格納する.
区間の最値を求めるアルゴリズムの中にもう一つのa[i]配列があり、i番目の数がいくらであるかを表す.
(その中でもlowbit(x)=x&(-x)という木の配列を学んだことは知っているでしょう...)
二、単点修正後の更新
1、メンテナンス区間和のアルゴリズムにおいて、このようにメンテナンス単点修正の
つまり、それを含む配列ごとに増加した値が加算されます.
2、メンテナンス区間の最大値を見るアルゴリズムでは、まず区間全体[1,n]を初期化する必要がある場合を見てみましょう.(すなわち、h[]配列はすべて0であり、a[]配列でh[]配列を更新する必要がある)
これは可能であり、そこで、数を更新するときにh[]配列をクリアし、配列a[]でh[]配列を更新するO(n*logn)のメンテナンス方法があります.
しかし、この複雑さは明らかに高すぎる.
xに対してxに移行できるのは,x-2^0,x-2^1,x-2^2,......,x-2^k(kは2^k=lowbit(x))つまりxdからx-lowbit(x)+1という区間を満たしています.これも私たちが維持する必要があります.
例:
x=1010000
= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3
= 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2
= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1
= 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0
したがって、各h[i]について、h[1...i-1]が正しいことを保証する前提で、h[i]値を再計算する時間複雑度はO(logn)であり、具体的な方法は以下の通りである.
これにより,ツリー配列メンテナンス区間とよく似たアルゴリズムを得ることができる.
このアルゴリズムの時間的複雑さはO((logn)^2)であるため,O((logn)^2)の時間内に最値の区間メンテナンスを完了できるようになった.
三、区間照会1、樹状配列の区間合を求めるアルゴリズムはこうである.
2、木の配列は区間の最大値を求めます:
直接区間合を求める方法は明らかにだめだ.
区間合では,[x,y]の区間合をクエリするため,[1,x−1]の合と[1,y]の合を求め,その後減算して[x,y]区間の合を得た.
区間の最値はこの性質がないので、考え方を変えることができます.
query(x,y)とし、[x,y]区間の最大値を表す
h[y]は[y,y-lowbit(y)+1]の最大値を表すからである.
したがって、次のように解くことができます.
y-lowbit(y)>xの場合、query(x,y)=max(h[y],query(x,y-lowbit(y))));すなわち、x−yという区間に含まれるy−lowbit(y)<=xであればquery(x,y)=max(a[y],query(x,y−1);この場合x-yの範囲を超えているので、y-lowbit(y)を直接使うことはできず、yを減らすしかありません.
この再帰的解は解を求めることができ,このような解の時間的複雑さがO((logn)^2)であることを証明できる.
具体的なコード:
時間の複雑さの証明:(バイナリに変えて見る)
yはLogn回変換後、xとは異なる最高位が少なくとも1ビット下がったため、最大で(logn)^2回変換を行う
例:
y = 1010000
x = 1000001
1010000
=> 1001111 => 1001110 =>1001100 =>1001000
=>1000111 => 1000110 => 1000100
=> 1000011 = > 1000010
=>1000001
=>1000000 < 1000001
最後にhdu 1754のコードを貼って、この問題は単点修正と区間クエリの最大値の問題です.
区間の最大値を維持してクエリーすると仮定します(最小値はmaxをminに変更すればいいです)
このアルゴリズムは、ツリー配列のメンテナンスとクエリー区間の和の方法と似ています.
一、配列の意味
1、メンテナンスとクエリー区間和のアルゴリズムにおいて、h[x]に格納されているのは[x,x-lowbit(x)+1]の各数の和であり、
2、区間最値を求めるアルゴリズムでは、h[x]は[x,x-lowbit(x)+1]の各数の最大値を格納する.
区間の最値を求めるアルゴリズムの中にもう一つのa[i]配列があり、i番目の数がいくらであるかを表す.
(その中でもlowbit(x)=x&(-x)という木の配列を学んだことは知っているでしょう...)
二、単点修正後の更新
1、メンテナンス区間和のアルゴリズムにおいて、このようにメンテナンス単点修正の
void updata(int k, int val)
{
while (k <= n)
{
h[k] += val;
k += lowbit(k);
}
} つまり、それを含む配列ごとに増加した値が加算されます.
2、メンテナンス区間の最大値を見るアルゴリズムでは、まず区間全体[1,n]を初期化する必要がある場合を見てみましょう.(すなわち、h[]配列はすべて0であり、a[]配列でh[]配列を更新する必要がある)
void updata(int k, int val)
{
while (k <= n)
{
h[k] = max(h[k], val);
k += lowbit(k);
}
} これは可能であり、そこで、数を更新するときにh[]配列をクリアし、配列a[]でh[]配列を更新するO(n*logn)のメンテナンス方法があります.
しかし、この複雑さは明らかに高すぎる.
xに対してxに移行できるのは,x-2^0,x-2^1,x-2^2,......,x-2^k(kは2^k
例:
x=1010000
= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3
= 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2
= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1
= 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0
したがって、各h[i]について、h[1...i-1]が正しいことを保証する前提で、h[i]値を再計算する時間複雑度はO(logn)であり、具体的な方法は以下の通りである.
h[x] = a[x];
lx = lowbit(x);
for (k=1; k1) h[x] = max(h[x], h[x-k]);
x += lowbit(x); これにより,ツリー配列メンテナンス区間とよく似たアルゴリズムを得ることができる.
void updata(int x)
{
int lx, k;
while (x <= n)
{
h[x] = a[x];
lx = lowbit(x);
for (k=1; k1)
h[x] = max(h[x], h[x-k]);
x += lowbit(x);
}
} このアルゴリズムの時間的複雑さはO((logn)^2)であるため,O((logn)^2)の時間内に最値の区間メンテナンスを完了できるようになった.
三、区間照会1、樹状配列の区間合を求めるアルゴリズムはこうである.
int query(int k)
{
int ans = 0;
while (k > 0)
{
ans += h[k];
k -= lowbit(k);
}
return ans;
}
2、木の配列は区間の最大値を求めます:
直接区間合を求める方法は明らかにだめだ.
区間合では,[x,y]の区間合をクエリするため,[1,x−1]の合と[1,y]の合を求め,その後減算して[x,y]区間の合を得た.
区間の最値はこの性質がないので、考え方を変えることができます.
query(x,y)とし、[x,y]区間の最大値を表す
h[y]は[y,y-lowbit(y)+1]の最大値を表すからである.
したがって、次のように解くことができます.
y-lowbit(y)>xの場合、query(x,y)=max(h[y],query(x,y-lowbit(y))));すなわち、x−yという区間に含まれるy−lowbit(y)<=xであればquery(x,y)=max(a[y],query(x,y−1);この場合x-yの範囲を超えているので、y-lowbit(y)を直接使うことはできず、yを減らすしかありません.
この再帰的解は解を求めることができ,このような解の時間的複雑さがO((logn)^2)であることを証明できる.
具体的なコード:
int query(int x, int y)
{
int ans = 0;
while (y >= x)
{
ans = max(a[y], ans);
for (--y; y-lowbit(y) >= x; y -= lowbit(y))
ans = max(h[y], ans);
}
return ans;
} 時間の複雑さの証明:(バイナリに変えて見る)
yはLogn回変換後、xとは異なる最高位が少なくとも1ビット下がったため、最大で(logn)^2回変換を行う
例:
y = 1010000
x = 1000001
1010000
=> 1001111 => 1001110 =>1001100 =>1001000
=>1000111 => 1000110 => 1000100
=> 1000011 = > 1000010
=>1000001
=>1000000 < 1000001
最後にhdu 1754のコードを貼って、この問題は単点修正と区間クエリの最大値の問題です.
#include
#include
#include
using namespace std;
const int MAXN = 3e5;
int a[MAXN], h[MAXN];
int n, m;
int lowbit(int x)
{
return x & (-x);
}
void updata(int x)
{
int lx, i;
while (x <= n)
{
h[x] = a[x];
lx = lowbit(x);
for (i=1; i1)
h[x] = max(h[x], h[x-i]);
x += lowbit(x);
}
}
int query(int x, int y)
{
int ans = 0;
while (y >= x)
{
ans = max(a[y], ans);
y --;
for (; y-lowbit(y) >= x; y -= lowbit(y))
ans = max(h[y], ans);
}
return ans;
}
int main()
{
int i, j, x, y, ans;
char c;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1; i<=n; i++)
h[i] = 0;
for (i=1; i<=n; i++)
{
scanf("%d",&a[i]);
updata(i);
}
for (i=1; i<=m; i++)
{
scanf("%c",&c);
scanf("%c",&c);
if (c == 'Q')
{
scanf("%d%d",&x,&y);
ans = query(x, y);
printf("%d
",ans);
}
else if (c == 'U')
{
scanf("%d%d",&x,&y);
a[x] = y;
updata(x);
}
}
}
return 0;
}