BIT ، ساختمان داده ای ساده ولی قدرتمند

BIT کلمه ای است که از حروف اول binary indexed tree گرفته شده است و ساختمان داده ای ساده ، سریع و قدرتمند است که در رابطه با مسائلی که با فراوانی تجمعی سر و کار دارند به کار می رود ، این ساختمان داده اولین بار در مقاله ای با عنوان A New Data Structure for Cumulative Frequency Tables توسط peter m. fenwick ارائه شد که به همین دلیل بسیاری آن را با عنوان fenwick tree نیز میشناسند.

در این آموزش با این ساختمان داده جذاب آشنا می شویم.

قبل از آشنایی با این ساختمان داده بهتر است یک مسئله ساده و یک راه حل ابتدایی برای آن ببینیم.

مسئله :

آرایه ای از n عدد به ما داده شده است میخواهیم دو عمل زیر را بر روی این آرایه انجام دهیم (فرض کنید اندیس اعداد از 1 شروع می شود) :

  • $getCum(i)$ : فراوانی تجمعی از اندیس یک تا اندیس i را محسابه کند.
  • $addValue(i,v)$ : مقدار v را به خانه متناظر با اندیس i اضافه کند.

حل

راه حل های مختلفی برای این مسئله وجود دارد که در اینجا به عمد یک راه حل ساده و ابتدایی را ارائه می دهیم تا بیشتر با فراوانی تجمعی و جدول فراوانی تجمعی آشنا شویم .برای سادگی فرض می کنیم که n+1 عدد داریم و اندیس صفر همیشه صفر است.

در اینجا و در ادامه آموزش آرایه اصلی را a می نامیم.

یک راه حل ساده بدین صورت است که یک آرایه هم طول با آرایه اصلی داشته باشیم ، این آرایه را FT می نامیم (مخفف Frequency Table). و $FT[i]$ را به صورت زیر تعریف می کنیم :

$$FT[i]=\sum_{j=1}^{i}a[j]$$

یا به عبارتی :

$$FT[i]=a[1]+a[2]+a[3]+...+a[i]$$

به صورت یک نمادگذاری خاص $FT[i]$ را به صورت زیر نیز نمایش می دهند که در ادامه به این نوع از نمادگذاری نیاز خواهیم داشت.

$$FT[i]=a[1...i]$$

با استفاده از این تعریف متد getCum را به صورت بسیار بهینه ای به صورت زیر می توانیم بنویسیم :


	int getCum(int i){
		return FT[i];
	}

همانطور که مشاهده می کنید زمان اجرای این متد از مرتبه $O(1)$ است ، ولی چندان خوشحال نباشد addValue همه چیز را خراب خواهد کرد.

اگر از این روش برای حل مسئله استفاده کنیم ، ناچاریم addValue را به شکلی بنویسیم که هر بار پس از اضافه کردن مقدار v به اندیس i ام ، جدول FT را نیز اصلاح کند ، یعنی باید addValue را به شکل زیر بنویسیم :


	void addValue(int i,int v){
		for(int j=i;j<FT.length;j++){
			FT[j]+=v;
		}
	}


همانطور که به سادگی قابل مشاهده است ، زمان اجرای این متد در بدترین حالت از مرتبه $O(n)$ است که برای مقادیر بزرگ n اصلاً قابل قبول نیست.

یک بحث تکمیلی :

معمولاً برای مقادیر بزرگ n صرفه جویی در حافظه یک امر مهم محسوب می شود ، در راه حل فوق پس از مقدار دهی اولیه FT دیگر به a نیاز نداریم و می توانیم آن را از حافظه پاک کنیم ، در این رابطه شاید بد نباشد متد ساده زیر را نیز تعریف کنیم :

  • $get(i)$ : این متد باید مقدار واقعی آرایه a در اندیس i را بر گرداند .

چون فرض می کنیم که a از حافظه پاک شده است و فقط FT را در اختیار داریم ، متد get را می توانیم به صورت زیر بنویسیم :


	int get(int i){
		return FT[i]-FT[i-1];
	}


با توجه به توضیحات فوق کد کامل این راه حل به صورت زیر خواهد بود (به همراه تست) :



public class FT {
	int FT[];
	public FT(int a[]){
		FT=new int[a.length];
		for(int i=1;i<FT.length;i++){
			FT[i]=FT[i-1]+a[i];
		}
	}
	
	int getCum(int i){
		return FT[i];
	}
	void addValue(int i,int v){
		for(int j=i;j<FT.length;j++){
			FT[j]+=v;
		}
	}
	int get(int i){
		return FT[i]-FT[i-1];
	}
	public static void main(String args[]){
		int a[]={0,4,-2,8,5,1,9,6,3,5,8,6,6,-3,5,2};
		FT ft=new FT(a);
		
		System.out.println("getCum(1) :\t"+ft.getCum(1));
		System.out.println("getCum(3) :\t"+ft.getCum(3));
		System.out.println("getCum(5) :\t"+ft.getCum(5));
		System.out.println("get(5) :\t"+ft.get(5));
		System.out.println("getCum(9) :\t"+ft.getCum(9));
		System.out.println("getCum(15) :\t"+ft.getCum(15));
		
		System.out.println("addValue(5,4)");
		ft.addValue(5, 4);
		System.out.println("getCum(1) :\t"+ft.getCum(1));
		System.out.println("getCum(3) :\t"+ft.getCum(3));
		System.out.println("getCum(5) :\t"+ft.getCum(5));
		System.out.println("get(5) :\t"+ft.get(5));
		System.out.println("getCum(9) :\t"+ft.getCum(9));
		System.out.println("getCum(15) :\t"+ft.getCum(15));
		
	}
	
}


خروجی تست :


getCum(1) :	4
getCum(3) :	10
getCum(5) :	16
get(5) :	1
getCum(9) :	39
getCum(15) :	63
addValue(5,4)
getCum(1) :	4
getCum(3) :	10
getCum(5) :	20
get(5) :	5
getCum(9) :	43
getCum(15) :	67

 

حالا آماده ایم تا همین مسئله را با BIT حل کنیم و از این طریق با BIT آشنا شویم.

حل مسئله با BIT :

فرض کنید آرایه BIT به شکل زیر تعریف شده باشد :

8 7 6 5 4 3 2 1 0 index
$a[1..8]$ $a[7]$ $a[5..6]$ $a[5]$ $a[1..4]$ $a[3]$ $a[1..2]$ $a[1]$ 0 BIT

ادامه : 

15 14 13 12 11 10 9 index
$a[15]$ $a[13..14]$ $a[13]$ $a[9..12]$ $a[11]$ $a[9..10]$ $a[9]$ BIT

فعلاً نگران ساختار عجیب و غریب آرایه BIT نباشید ، نگران این نباشید که این تعریف از کجا آمده است ، نگران نحوه پر کردن این آرایه و ساخت آن نیز نباشید ، حتی نگران اندیس های بزرگتر از 15 نیز نباشید ، فعلاً فرض کنید که شخص دیگری وجود دارد که می تواند آرایه a را از ما بگیرد  و آرایه BIT را مبتنی بر تعریف فوق برای ما مقدار دهی کند.

نکته : اگرچه در مورد نمادگذاری فوق قبلاً توضیح دادم ولی برای تاکید مجدد باید اشاره کنم که منظور از  $a[9..10]$ همان $a[9]+a[10]+a[11]+a[12]$ است ، منظور از $a[5..6]$ نیز $a[5]+a[6]$ است و بقیه موارد نیز به همین ترتیب ...

سوال : از روی تعریف آرایه BIT  در قسمت قبل $getCum(11)$ یعنی مجموع عناصر آرایه a از اندیس 1 تا 11 را محاسبه کنید.

جواب :

متغیر ix و sum را به صورت زیر تعریف می کنیم :

$$sum=0$$
$$ix=11$$

گام اول :

$$sum+=BIT[ix]$$

در این گام چندان نکته ای وجود نداشت ، قسمت جذاب کار از گام های بعد شروع می شود.

همه چیز در BIT مبتنی بر شکل دودویی اعداد است ، در حقیقت BIT الهامی از این موضوع است که هر عدد صحیح را می توان به صورت مجموع توان هایی از عدد 2  نوشت که به این تعریف شکل دودویی عدد می گوییم که در دنیای کامپیوتر این شکل از اعداد بسیار شناخته شده است.

اجازه دهید که شکل دودویی عدد 11 را با هم مشاهده کنیم :

$$bin(11)=1011$$

برای گام اجرای گام دوم سمت راست ترین 1 از نمایش دودویی فوق را حذف می کنیم.

یعنی :

گام دوم :

$$ix=1010(bin)=10$$

باز هم مانند قبل عمل می کنیم :

$$sum+=BIT[ix]$$

گام سوم :

مجدداً سمت راست ترین 1 از شکل دودویی ix را حذف می کنیم.

یعنی :

$$ix=1000(bin)=8$$

و برای محاسبه sum باز هم مثل قبل عمل می کنیم :

$$sum+=BIT[ix]$$

گام چهارم :

مجدداً سمت راست ترین 1 از نمایش دودویی ix را حذف می کنیم.

$$ix=0000(bin)=0$$

در این گام ix صفر می شود و به کارمان خاتمه می دهیم.

اگر گام های فوق را با دقت دنبال کرده باشید حتماً متوجه شده اید که در پایان کار sum به صورت زیر است  :

$$sum=(BIT[11])+(BIT[10])+(BIT[8])$$

اگر به جای BIT تعاریف متناظر قرار دهیم خواهیم داشت :

$$sum=(a[11])+(a[9..10])+(a[1..8])=a[1]+a[2]+..+a[11]$$

مشاهده می کنید که $getCum(11)$ به سه گام ما را به جواب رساند.(سه عمل جمع) .اگر به جای 11 سایر اعداد را امتحان کنید بازهم نتیجه درست خواهد بود و مشاهده می کنید که تعریف عجیب و غریب فوق (یعنی نوع تعریف آرایه BIT) به سرعت ما را به جواب می رساند.

با توجه به توضیحات این قسمت $getCum(i)$ را می توانیم به صورت زیر پیاده سازی کنیم :


	int getCum(int i){
		int ix=i;
		int sum=0;
		while(ix>0){
			sum+=BIT[ix];
			ix=removeLastOne(ix);
		}
		return sum;
	}

زمان اجرای متد فوق به تعداد یک های موجود در i بستگی دارد یعنی چیزی کمتر از $log(n)$ ، لذا در بدترین حالت زمان اجرای این متد از مرتبه $O(log(n))$ است.

ولی یک نکته مهم :

چگونه می توان removeLastOne را پیاده سازی کرد؟

این سوال نکته بسیار مهم این ساختمان داده است ، معمولاً به دلیل استفاده از زبان های برنامه نویسی شیک و تر و تمیزی مثل جاوا و سی و غیره چندان با شکل دودویی اعداد سر و کار نداریم ، اگرچه ممکن است به عنوان شخصی که در دنیای کامپیوتر فعالیت می کند در پروفایل های خود در شبکه های اجتماعی حرف از اعداد دودویی و بیت و بایت و غیره بزنیم ولی معمولاً در عمل درک چندان شفافی از اعداد دودویی و ویژگی های آن ها نداریم .برای حذف سمت راست ترین یک ابتدا با یک عمل جذاب آشنا می شویم.

یک عمل جذاب : 

شاید تعجب کنید که عمل $ixAND(-ix)$ معادل سمت راست ترین 1 در عدد ix است.

به عنوان مثال نمایش دودویی عدد 20 در یک سیستم 8 بیتی به صورت 00010100 است و نمایش دودویی 20- نیز در همین سیستم به صورت 11101100 است که AND این دو مقدار برابر با 00000100 خواهد بود. (با تعریف متمم و متمم دو این موضوع قابل اثبات است که در اینجا به این موضوع نمی پردازیم).

با توجه به عمل جذاب فوق متد removeLastOne را می توان به صورت بسیار بهینه ای به صورت زیر نوشت :


	int removeLastOne(int ix){
		return ix-(ix&-ix);
	}

برای اجرای سریعتر متد getCum بهتر است فراخوانی متد removeLastOne را حذف کنیم و getCum را به صورت زیر بنویسیم :


	int getCum(int i){
		int ix=i;
		int sum=0;
		while(ix>0){
			sum+=BIT[ix];
			ix=ix-(ix&-ix);
		}
		return sum;
	}

نکته : کد جاوای زیر برای آشنایی بیشتر با متد removeLastOne است :



public class RemoveLastOne {
	
	public RemoveLastOne(){
		int n=50;
		for(int i=1;i<n;i++){
			System.out.println("-----");
			System.out.println("[ "+i+" ]");
			int ix=i;
			while(ix>0){
				System.out.println(ix+" ("+Integer.toBinaryString(ix)+")");
				ix=removeLastOne(ix);
			}
		}
	}
	
	
	int removeLastOne(int ix){
		return ix-(ix&-ix);
	}
	
	public static void main(String[] args) {
		new RemoveLastOne();
	}

}


خروجی برنامه فوق را خودتان تولید و مطالعه کنید.

ساختار درختی BIT : 

با متد getCum و نحوه پیاده سازی آن آشنا شدیم ولی هنوز با ساختار آرایه BIT آشنایی نداریم و قانع نشده ایم که متد getCum چرا درست کار می کند؟ چرا برای BIT از واژه tree استفاده می کنیم؟ و اینکه ایده اصلی BIT از کجا آماده است؟

احتمالاً جواب سوال آخر خط قبل را زودتر از بقیه سوال های متوجه شده اید ، تمام ایده های مربوط به BIT از نمایش دودویی اعداد گرفته شده است  حتی اسم این ساختمان داده نیز نشان دهنده این موضوع است.

اگر به مثال بخش به شکل یک درختی فرضی نگاه کنیم متوجه می شویم که مسیر زیر را پیموده ایم (از گره 11 تا گره 0):

در داخل هر گره اندیس آن نوشته شده است (دقت کنید که BIT در حقیقت یک آرایه است که مفهومی درخت گونه دارد ، مثل heap). در کنار هر گره شکل دودویی اندیس آن و وظیفه آن نیز نوشته شده است.

منظور از وظیفه این است که مثلاً گره 11 وظیفه دارد که $a[11]$ را در خود نگه داری کند و گره 10 وظیفه دارد $a[9]+a[10]$ را در خود نگه داری کند و بقیه گره ها نیز به همین صورت ...

گره 0 یک گره خاص است که فقط مقدار 0 را در خود نگه داری می کند و نشان دهنده ریشه درخت فرضی است.

همانطور که قبلاً مشاهده کردیم در BIT برای رسیدن به فراوانی تجمعی متناظر با اندیس i به k زیر مجموعه نیاز داریم که k تعداد یک های نمایش دودویی عدد i است ، به عنوان مثال برای 11 به سه زیر مجموعه نیاز داشتیم (مجموعه 1 تا 8 ، مجموعه 9 تا 10 و مجموعه 11).

با در نظر گرفتن همین نکته به نتیجه زیر می رسیم :

اعدادی (اندیس هایی) که تنها شامل یک 1 در نمایش دودویی خود باشند باید با یک گام ما را به جواب برسانند و این یعنی باید شامل مجموع تمام عدد قبل از خود باشند.

به عبارت دیگر اگر i توانی از دو باشد (مانند 1 ، 2 ، 4 و 8) در نمایش دودویی شامل تنها یک 1 خواهد بود و باید $a[1...i]=a[1]+a[2]+...+a[i]$ را در خود نگه داری کند.

پس نتیجه می گیریم که اندیس هایی که توان عدد دو هستند (تنها یک 1 در نمایش دودودیی خود دارند) فرزندان سطح یک ریشه درخت (گره صفر) هستند.

تصویر زیر این موضوع را نمایش می دهد :

احتمالاً لازم نیست اشاره کنم که فرزندان سطح دوم گره هایی هستند که دو 1 در نمایش دودویی خودشان دارند. (با کمی تامل در مورد نحوه عملکرد getCum به راحتی متوجه نحوه سطح بندی درخت می شوید.)

می دانیم که گره های سطح دو اندیس هایی هستند که در دو 1 در نمایش دودویی آن ها وجود دارد ولی رابطه گره های فرزند و پدر به چه شکل است؟

در تعریف getCum دیدیم که از پایین به بالا با پیمایش مسیری در داخل درخت فرضی هر بار برای به دست آوردن گره پدر سمت راست 1 در نمایش دودویی را حذف می کردیم پس اگر گره i یک گره مفروض باشد که نمایش دودویی آن به شکل xy باشد که در آن y رشته ای تشکیل یافته شده از صفر باشد و x رشته ای مرکب از صفر و یک باشد که به یک ختم می شود آنگاه فرزندان گره i باید دارای یک 1 در بخش y باشند. به عنوان مثال اگر i به صورت x0000 باشد (یعنی y=0000 باشد) آنگاه فرزندان i دارای یک 1 در بخش y هستند پس فرزندان i به صورت x0001 و x0010 و x0100 و x1000 خواهند بود.

مثال

گره هشت دارای نمایش دودویی 1000 است پس فرزندان آن 1001 (نه) و 1010 (ده) و 1100 (دوازده) خواهند بود.

گره های سطح دو باید با دو گام ما را به جواب برسانند یعنی با اجتماع دو زیر مجموعه به فراوانی تجعی می رسیم ، لذا هر گره در سطح دو وظیفه دارد اطلاعات قسمت هایی که گره پدر آن ها را شامل نمی شود در خود نگه داری کند ، به عنوان مثال گره 12 فرزند گره 8 است ، گره 8 مجموع $a[1..8]$ را در خود نگه داری می کند پس گره دوازده باید مجموع سایر اعداد قبل از 12 یعنی $a[9..12]$ را در خود نگه داری کند (به همین طریق مفهوم سایر گره ها نیز قابل استخراج است).

نکته : دقت کنید که در حقیقت هیچ درختی وجود ندارد و تمام تعاریف فوق تنها قرار داد هستند ، قرار دادی که خودمان آن ها وضع کردیم و خودمان بر اساس آن ها استنتاج می کنیم.

سایر سطع های این درخت به همین صورت قابل تعریف هستند و شکل نهایی درخت برای 15 عدد به صورت زیر خواهد بود :

نکته : درخت فوق یک درخت مفهومی است و بیان گر نحوه دسترسی اندیس ها با استفاده از متد getCum است ، و در حقیقت همین getCum باعث می شود که آرایه BIT به این شکلی که ارائه شد تعبیر شود.

آرایه BIT را به شکل دیگری نیز نمایش می دهند که مفهوم بازه ها و نحوه پوشش آن ها را بهتر شرح می دهد :

شکل فوق دید کلی بهتری به ما می دهد ، به عنوان مثال به راحتی از شکل فوق می توان فهمید که گره 12 موظف است $a[9]+a[10]+a[11]+a[12]$ را نگه داری کند ، به علاوه پدر هر گره در تعریف متد getCum نیز به سادگی قابل مشاهده است.

addValue :

به قسمت مهم و عجیب و غریب تر رسیدیم ، می خواهیم متد $addValue(i,v)$ را به صورتی تعریف کنیم که مقدار v را به اندیس i اضافه کند.

به وضوح می دانیم که هر اندیس i در BIT  ، عدد متناظر با آن اندیس یعنی $a[i]$ را شامل می شود ( کافی است به شکل ها و تعاریف قبلی مراجعه کنید). 

از طرفی علاوه بر اندیس i اندیس های دیگری نیز ممکن است وجود داشته باشند که مقدار $a[i]$ را شامل شوند ، که در این صورت در هنگام پیاده سازی متد addValue باید این بازه ها را نیز مد نظر قرار دهیم.

به عنوان مثال گره 5 را در نظر بگیرید اگر بخواهیم به مقدار این گره یک مقدار خاص اضافه کنیم باید سایر گره هایی که اندیس 5 را شامل می شوند نیز به روز کنیم ، با مراجعه به تعریف و تصاویر قبلی متوجه می شویم که برای به روز رسانی مقدار گره 5 باید مقدار گره های 6 و 8 نیز به روز رسانی شوند.

به عنوان مثال دیگر با به روز رسانی مقدار گره 9 باید مقدار گره های 10 و 12 را نیز به روز رسانی کنیم.

پس باید راهی برای ارتباط بین این اعداد پیدا کنیم .

چه ارتباطی بین 5 و 6 و 8 وجود دارد؟ چه ارتباطی بین 9 و 10 و 12 وجود دارد؟

جواب باز هم در شکل دودویی این اعداد نهفته است.

به عنوان مثال به شکل دودویی عدد 5 نگاه می کنیم :

$$0101$$

اگر عمل جذابی که قبلاً گفته شد را بر روی 5 اعمال کنیم عدد زیر به دست می آید  (عددی که معادل آخرین 1 در نمایش دودویی عدد 5 است) :

$$0001$$

اگر این دو مقدار را با هم جمع کنیم به عدد 6 می رسیم!!

$$0101+0001=0110$$

اگر آن عمل جذاب ($ixAND(-ix)$) را بر روی عدد 6 انجام دهیم عدد زیر به دست می آید (عدد متناظر با آخرین یک در نمایش دودویی عدد 6) :

$$0010$$

حال اگر این دو عدد را با هم جمع کنیم به 8 می رسیم.

$$0110+0010=1000$$

اگر بار دیگر همین عمل را انجام دهیم به 16 می رسیم که عددی بزرگتر از آرایه مورد نظر ماست.

اجازه دهید با 9 نیز این عملیات را امتحان کنیم.

شکل دودویی عدد 9 به صورت زیر است :

$$1001$$

با توجه به روش قبل خواهیم داشت :

$$1001+0001=1010$$

یعنی به 10 خواهیم رسید.

با تکرار همین عمل خواهیم داشت :

$$1010+0010=1100$$

که همان عدد 12 است که انتظار آن را داشتیم.

مشاهده می کنید که متدد addValue را می توان کاملاً بر عکس متد getCum نوشت ، در متد getCum سمت راست ترین 1 را از اندیس مورد نظر حذف می کردیم ، در اینجا سمت راست ترین 1 را به عدد مورد نظر اضافه می کنیم، پس متد addValue را می توانیم به صورت زیر بنویسیم :


	void addValue(int i,int v){
		int ix=i;
		while(ix<BIT.length){
			BIT[ix]+=v;
			ix=ix+(ix&-ix);
		}
	}

تحلیل متد addValue کمی دشوار تر است زیرا در اینجا از تعداد یک ها و صفر ها اطلاعی نداریم و نمی توانیم این متد را بر اساس تعداد یک ها یا صفر ها تفسیر کنیم .

اگر ترتیب گره ها در متد addValue را تعقیب کنیم می بینم پیمایش گره ها این بار با پیمایش گره ها در متد getCum متفاوت است. به عنوان مثال در اینجا از گره 5 به 6 و سپس 8 می رویم ، یا از گره 9 به گره 10 و سپس 12 می رویم. اگر ترتیب پیمایش گره ها را به دست بیاوریم و درخت متناظر آن را رسم کنیم به شکل زیر می رسیم :

همانطور که مشاهده می کنید شکل ظاهری این درخت دقیقاً شبیه درختی است که در پیمایش گره ها در متد getCum  وجود داشت ، فقط اندیس گره ها متفاوت است ولی اگر دقت کنید حتی بین اندیس گره ها نیز یک رابطه بسیار ساده وجود دارد ، اندیس گره های درخت پیمایش متد addValue برابر است با تفریق اندیس گره های درخت پیمایش متد getCum از عدد 16 !.

موضوع فوق یک موضوع تصادفی نیست ، صحت عملکرد متد های getCum و addValue نیز تصادفی نیست ، درک دقیق تر این مسائل نیازمند آن است که فلسفه اصلی ساخت BIT را توضیح دهیم که در حقیقت راهی برای فشرده سازی درخت های دودویی بود که در این آموزش به این مباحث نمی پردازیم.

با توجه به توضیحات فوق پیچیدگی زمان متد addValue نیز دقیقاً مشابه متد getCum است و از مرتبه $O(log(n))$ است.

متد get :

برای به دست آوردن مقدار واقعی در اندیس i (همان $a[i]$ ) با استفاده از BIT می توانیم به صورت زیر عمل کنیم که حاصل دوبار فراخوانی متد getCum است و باز هم از مرتبه $O(log(n))$ خواهد بود ، البته راه حل سریع تری نیز برای این موضوع وجود دارد که به آن نمی پردازیم (می توانید به مقاله اصلی مراجعه کنید و یا اینکه چندان در مصرف حافظه صرفه جویی نکنید و آرایه a را نیز نگه داری کنید که این راه حل برای بسیاری از کاربرد ها مناسب تر است).


	int get(int i){
		return getCum(i)-getCum(i-1);
	}

با توجه به مطالب بالا کد این ساختمان داده را می توان به شکل زیر نوشت (به همراه تست). توجه کنید که برای ساخت اولیه BIT از n بار فراخوانی متد addValue استفاده می کنیم لذا ساخت اولیه BIT از مرتبه $O(nlog(n))$ خواهد بود.



public class BIT {
	int BIT[];
	public BIT(int a[]){
		BIT=new int[a.length];
		for(int i=1;i<BIT.length;i++){
			addValue(i,a[i]);
		}
	}
	
	int getCum(int i){
		int ix=i;
		int sum=0;
		while(ix>0){
			sum+=BIT[ix];
			ix=ix-(ix&-ix);
		}
		return sum;
	}

	void addValue(int i,int v){
		int ix=i;
		while(ix<BIT.length){
			BIT[ix]+=v;
			ix=ix+(ix&-ix);
		}
	}
	int get(int i){
		return getCum(i)-getCum(i-1);
	}
	public static void main(String args[]){
		int a[]={0,4,-2,8,5,1,9,6,3,5,8,6,6,-3,5,2};
		BIT ft=new BIT(a);
		
		System.out.println("getCum(1) :\t"+ft.getCum(1));
		System.out.println("getCum(3) :\t"+ft.getCum(3));
		System.out.println("getCum(5) :\t"+ft.getCum(5));
		System.out.println("get(5) :\t"+ft.get(5));
		System.out.println("getCum(9) :\t"+ft.getCum(9));
		System.out.println("getCum(15) :\t"+ft.getCum(15));
		
		System.out.println("addValue(5,4)");
		ft.addValue(5, 4);
		System.out.println("getCum(1) :\t"+ft.getCum(1));
		System.out.println("getCum(3) :\t"+ft.getCum(3));
		System.out.println("getCum(5) :\t"+ft.getCum(5));
		System.out.println("get(5) :\t"+ft.get(5));
		System.out.println("getCum(9) :\t"+ft.getCum(9));
		System.out.println("getCum(15) :\t"+ft.getCum(15));
		
	}
	
}


نکته : همین کد را در صفحه انگلیسی ویکی پدیای مربوط به این ساختمان داده به آدرس https://en.wikipedia.org/wiki/Fenwick_tree نیز قرار داده ام ، امیدوارم کاربران و برنامه نویسان ایرانی بیشتر به ویکی پدیا اهمیت دهند و زمان هایی را برای افزایش اطلاعات ویکی پدیا صرف کنند (سعی کنیم با مراجعه به سایت هایی مثل ویکی پدیا و stackoverflow همیشه مصرف کننده نباشیم و گاهی نیز کمک کننده باشیم. "همه چیز را همگان دانند" پس در اشتراک دانسته هایمان خسیس نباشیم)

مطالب دیگری نیز در رابطه با این ساختمان داده وجود دارند که در اینجا به آن ها نمی پردازیم ، در این آموزش فقط متد های اصلی و بسیار مهم این ساختمان داده را بیان کردیم.

با توجه به تمام توضیحات بالا متوجه می شویم که این ساختمان داده دارای مزیت های زیر است :

  • کد آن بسیار کوتاه است و برای مسابقات الگوریتمی به سرعت می توان آن را پیاده سازی کرد.
  • اندازه آرایه آن هم اندازه با آرایه اصلی است لذا مصرف حافظه آن از مرتبه $O(n)$ است.
  • متد های getCum و addValue بسیار سریع هستند و تعداد گام های آن ها حتی از log n نیز کمتر است.
  • به راحتی قابل توسعه به فضاهای دو بعدی و بیشتر است (در ادامه خواهیم دید).

معایب :

  • یک عیب اصلی این ساختمان درک پیچیدگی آن است ، معمولاً نگاشت مسئله به راه حلی که بتوان در آن از BIT استفاده کرد دشوار است و در بسیاری از موارد استفاده از segment tree ساده تر است.

BIT دو بعدی :

یک مزیت اصلی BIT  که به آن کاربرد عملی (عملی تر از مسابقات الگوریتمی) نیز می دهد این است که به راحتی قابل توسعه به حالت های دو بعدی و بیشتر است.برای این کاربرد باید یک BIT ای از BIT داشته باشیم ، یعنی یک BIT داشته باشیم که بر خلاف حالت قبل که هر خانه آن یک عدد بود این بار هر خانه از BIT خود نیز یک آرایه دیگر است که به صورت BIT تفسیر می شود.

چون با فضای دو بعدی سر و کار داریم از این به بعد هر عملیات به دو اندیس x و y نیاز دارد.

ابتدا متد addValue را مشاهده می کنیم :


	void addValue(int x, int y, int val) {
		while (x < MAX_X) {
			addValueY(x, y, val);
			x += (x & -x);
		}
	}

بسیار شبیه حالت قبل است ، با این تفاوت که قبلاً یک آرایه یک بعدی داشته لذا سریعاً مقدار val را به خانه متناظر با اندیس x اضافه می کردیم ولی اینبار متد addValueY را فراخوانی می کنیم ، این متد با هر سطری که با اندیس x مشخص می شود به صورت یک BIT یک بعدی رفتار می کند. (همانطور که گفتم BIT ای از BIT داریم).

لذا addValueY همانند مانند قبل یک BIT یک بعدی است (دقت کنید که در داخل متد addValueY مقدار x تغییر نمی کند)


	void addValueY(int x, int y, int val) {
		while (y < MAX_Y) {
			BIT[x][y] += val;
			y += (y & -y);
		}
	}

متد getCum را نیز مانند حالت یک بعدی می نویسیم با این تفاوت که این بار هر خانه از آرایه یک مقدار نیست که آن را با sum جمع کنیم ، بلکه هر خانه خود نیز یک BIT است پس باید مانند یک BIT با آن عمل کنیم یعنی متد getCumY را فراخوانی کنیم تا نتیجه را برای سطر x  برای ما محاسبه کند :


	int getCum(int x, int y) {
		int sum = 0;
		while (x > 0) {
			sum += getCumY(x, y);
			x -= (x & -x);
		}
		return sum;
	}

بدون نیاز به توضیح خودتان نیز می توانید ساختار getCumY  را حدس بزنید :


	int getCumY(int x, int y) {
		int sum = 0;
		while (y > 0) {
			sum += BIT[x][y];
			y -= (y & -y);
		}
		return sum;
	}

با توجه به توضیحات بالا کد کامل BIT دو بعدی به همراه تست به صورت زیر خواهد بود :


public class BIT2D {
	int BIT[][];
	int MAX_X;
	int MAX_Y;

	public BIT2D(int a[][], int n, int m) {
		MAX_X=n;
		MAX_Y=m;
		BIT=new int[MAX_X][MAX_Y];
		for(int i=1;i<n;i++){
			for(int j=1;j<m;j++){
				addValue(i,j,a[i][j]);
			}
		}
	}

	void addValueY(int x, int y, int val) {
		while (y < MAX_Y) {
			BIT[x][y] += val;
			y += (y & -y);
		}
	}

	void addValue(int x, int y, int val) {
		while (x < MAX_X) {
			addValueY(x, y, val);
			x += (x & -x);
		}
	}

	int getCumY(int x, int y) {
		int sum = 0;
		while (y > 0) {
			sum += BIT[x][y];
			y -= (y & -y);
		}
		return sum;
	}

	int getCum(int x, int y) {
		int sum = 0;
		while (x > 0) {
			sum += getCumY(x, y);
			x -= (x & -x);
		}
		return sum;
	}
	public static void main(String[] args) {
		int a[][]={
				{0,	0,	0,	0,	0,	0},
				{0,	1,	2,	3,	4,	5},
				{0,	-1,	-2,	-3,	-4,	-5},
				{0,	0,	0,	3,	1,	1},
				{0,	1,	2,	3,	4,	5}
		};
		int n=a.length;
		int m=a[0].length;
		BIT2D b2=new BIT2D(a,n,m);
		System.out.println(b2.getCum(1,1));
		System.out.println(b2.getCum(1,2));
		System.out.println(b2.getCum(1,3));
		System.out.println(b2.getCum(1,4));
		System.out.println(b2.getCum(1,5));
		System.out.println(b2.getCum(2,1));
		System.out.println(b2.getCum(2,2));
		System.out.println(b2.getCum(2,3));
		System.out.println(b2.getCum(2,4));
		System.out.println(b2.getCum(2,5));
		System.out.println(b2.getCum(4,1));
		System.out.println(b2.getCum(4,2));
		System.out.println(b2.getCum(4,3));
		System.out.println(b2.getCum(4,4));
		System.out.println(b2.getCum(4,5));


	}
}


خروجی تست :


1
3
6
10
15
0
0
0
0
0
1
3
9
14
20

دقت کنید که هدف فراوانی تجمعی است لذا منظور از $b2.getCum(4,3)$ جمع تمام عناصر از سطر 1 و ستون 1 تا سطر 4 و ستون 3 است.

نکته : متد های getCum و addValue در BIT  دو بعدی از مرتبه $O(log(n)log(m))$ هستند و زمان اجرای ساخت آن نیز از مرتبه $O(nmlog(n)log(m))$ است.

به همین سادگی می توان BIT را برای فضاهای بزرگتر (سه بعدی و بیشتر ) نیز به کار برد . 

 

منابع مطالعاتی بیشتر:

به نظر خودم بهترین منبع برای یادگیری BIT و مباحث مختلف آن مطالعه مقاله اصلی است که از طریق لینک زیر می توانید به آن دسترسی داشته باشید :

 A New Data Structure for Cumulative Frequency Tables 

آموزشی هم در سایت topcoder.com وجود دارد که مسائل جالب و متنوعی را با BIT حل می کند :

https://www.topcoder.com/community/data-science/data-science-tutorials/b...

 

تمرین :

اگرچه BIT ظاهر ساده ای دارد ولی نگاشت مسائل مختلف به آن برای حل مسئله معمولاً دشوار است و بهترین راه یادگیری تمرین ، تمرین و حل مسائل مختلف است

معمولاً مسائل سایت acm.timus.ru جذاب تر هستند :

http://acm.timus.ru/problem.aspx?space=1&num=1090

http://acm.timus.ru/problem.aspx?space=1&num=1028

هر دو مسئله فوق با BIT یک بعدی قابل حل هستند.

مسئله زیر نیز با BIT حل می شود :

http://www.spoj.com/problems/DQUERY

برای حل مسئله با BIT دو بعدی می توانید مسئله زیر را حل کنید :

http://www.spoj.com/problems/MATSUM

مسائل بیشتری را می توانید در لینک زیر مشاهده کنید (البته دقت کنید که به جز BIT راه حل های دیگری نیز وجود دارند)

http://a2oj.com/Category.jsp?ID=26

 

دیدگاه‌ها

5

بسیار عالی...من همیشه از وقتی با سایتتون اشنا شدم مطالبش رو دنبال میکنم...خصوصا مباحث الگوریتم و آندروید...

ممنون از نظرتون ، خوشحالم که می بینم مباحث الگوریتمی هم طرفدار دارن ، خودم علاقه شخصیم بیشتر مباحث الگوریتمیه ولی خب چون نوشتنشون به وقت و حوصله بیشتری نیاز داره کمتر می نویسم و بیشتر مطالب مربوط به کدنویسی (مثل اندروید) می نویسم.

اره شما درست می فرمایید.. ولی واقعا الگوریتم یکی از مباحث جذاب و پر چالش هست....ولی کمتر بهش می پردازند..
بنظرم این مباحث مربوط به راه حل پویا خیلی جذابند.

سلام آقای رمضان زاده..ببخشید امکانش هست ایمیل تون بدید. من میخواستم در مورد یکسری موضوعات ازشما مشورت بگیرم..

سلام پایین سایت هست

افزودن دیدگاه جدید

Plain text

  • تگ‌های HTML مجاز نیستند.
  • نشانی صفحه‌ها وب و پست الکترونیک بصورت خودکار به پیوند تبدیل می‌شوند.
  • خطوط و پاراگراف‌ها بطور خودکار اعمال می‌شوند.