الگوریتم فنویک

نویسنده: HamidReza_H
ارسال‌شده در:
دیدگاه‌ها: 2

برای چند تا از بچه ها که میخواستن این الگوریتمو بدونم گذاشتم این بلاگو

الگوریتم فنویک الگوریتمی پر سرعت برای حل این سوال است :

فرض کنید ارایه a به اندازه n که در ابتدا همه مقادیر آن برابر 0 هستند به ما داده شده است، می خواهیم اعمال زیر را روی این آرایه انجام دهیم:

  • به درایه x-ام ، val واحد اضافه کن.

  • مجموع اعداد درایه x-ام تا درایه y-ام را به دست بیاور

خوب میخواهیم الگوریتمی که ارایه میدهیم هر دو عمل را در $ o(lgn) $  انجام بدهد

برای این کار fen را تعریف میکنیم فرض کنید کوچکترین بیت ۱ عدد x برابر با r باشد در این صورت:

$fen[x]=a[x-2^r+1]+a[x-2^r+2]+a[x-2^r+3]+...+a[x]$

به $x-2^r$ میگوییم از این به بعد $f(x)$

خوب فرض کنید که توانستیم $fen$ را تاکنون درست بسازیم عمل نوع دوم به این صورت محاسبه میشود:

$pre[x]=a[0]+a[1]+...+a[x]$

$pre[y]=a[0]+a[1]+...+a[y]$

$sum[x...y]=pre[y]-pre[x-1]$

خوب پس اگر بتوانیم هر$ pre $را محاسبه کنیم مسیله حل است خوب$ pre $میشود:

$pre[x]=fen[x]+fen[f(x)]+fen[f(f(x))]+...$

خوب اکنون میخواهیم عمل نوع اول را درست انجام بدهیم عمل نوع ۱ هم به این صورت میشود

بعد از این که به درایه i-ام، مقدار $val$ را اضافه می کنیم، باید به همه$ fen[j] $هایی که i در بازه j قرار می گیرد، مقدار$ val $را اضافه کنیم. برای این کار ابتدا به$ fen[i] $، این مقدار را اضافه میکنیم، سپس کوچکترین بیت 1 در i را به آن اضافه می کنیم و تا زمانی که$ i<=n $باشد این کار را ادامه می دهیم

خوب اکنون تحلیل اردر میکنیم برای عمل نوع دو از انجا که هر دفعه یک بیت ۱ از x در عمل$ f(x) $حذف میشود پس اردر$ lgn $میشود

برای عمل نوع اول هم هر دفعه کوچکترین بیت حداقل یکی بیشتر میشود پس بازهم اردر$ lgn $میشود

خوب میتونید با سرچ تو گوگل و این حرفا به این نتیجه برسید که

$f(x)=x-(x\&(-x))$

پس کد هر دو میشود:

int sum(int x)
{
       int ret=0;
       for (;x;x-=x&-x) ret+=fen[x];
       return ret;
}

void add(int p,int val)
{
         for (;p<=n;p+=p&-p) fen[p]+=val;
}

 برای اون قسمت$ f(x) $:

https://en.wikipedia.org/wiki/Two's_complement

ارسال‌شده در:
ATofighi نوشته:
به صفحه‌ی اصلی اضافه شد :xD: 
ارسال‌شده در:
BardiaAF نوشته:
خیلی خوب بود. مرسی  :دی