Tata: Created page with "* เอามาจาก wiki.acioi.in.th '''Fenwick Tree''' หรือ '''Binary Index Tree''' * ใช้แก้ปัญหาที่ว่า "ถ้าต้อ..."

2019-03-06T17:22:54Z

Created page with "* เอามาจาก wiki.acioi.in.th '''Fenwick Tree''' หรือ '''Binary Index Tree''' * ใช้แก้ปัญหาที่ว่า "ถ้าต้อ..."

New page

* เอามาจาก wiki.acioi.in.th
'''Fenwick Tree''' หรือ '''Binary Index Tree'''

* ใช้แก้ปัญหาที่ว่า "ถ้าต้องการใส่ค่า v ให้กับตารางช่องที่ i (พูดง่ายๆคือ arr[i] += v) สลับกับ การถามว่าผลบวกค่าทุกค่าในตารางช่องที่ 1 ถึงช่องที่ x มีค่าเท่าไหร่ (ผลบวกตั้งแต่ arr[1] ถึง arr[x]) ทำสลับอย่างงี้ไปเรื่อยๆ"

'''สมมติให้'''
* Update(x, v) คือ ฟังก์ชันใส่ค่า v ในช่องที่ x
* FreqTo(x) คือ ฟังก์ชันหาผลรวมตั้งแต่ช่องที่ 1 ถึงช่องที่ x
* FreqAt(x) คือ ฟังก์ชันหาค่าช่องที่ x

== เปรียบเทียบระหว่าง Array กับ Fenwick Tree ==
'''ถ้าใช้ Array แก้โจทย์ข้อนี้'''
* Update(x, v) ::ใช้เวลา O(x)
* FreqTo(x) ::ใช้เวลา O(x)
* FreqAt(x) ::ใช้เวลา O(1)

'''ถ้าใช้ Fenwick Tree แก้โจทย์ข้อนี้'''
* Update(x, v) ::ใช้เวลา O(log x)
* FreqTo(x) ::ใช้เวลา O(log x)
* FreqAt(x) ::ใช้เวลา O(log x)

== ตัวอย่าง Code ของ Fenwick Tree (1 มิติ) ==
<syntaxhighlight lang="c++" line='line'>
/*
DATA STRUCTURE
+ Fenwick Tree
+ Update(x, value)
:: O(lg n)
:: Add value at position[x]
+ FreqTo(x)
:: O(lg n)
:: Query summation from postion [1] to position[x]
- Memory O(max_size)
AUTHOR
+ Roos
*/
#include<stdio.h>
#define MAXSIZE 1000000
int tree[MAXSIZE+1], n;
void update(int x, int value)
{
for(int i=x; i<=MAXSIZE; i+=(i&-i))
tree[i] += value;
}
int freqTo(int x)
{
int sum = 0;
for(int i=x; i>=1; i-=(i&-i))
sum += tree[i];
return sum;
}
int main()
{
while(1)
{
char cmd[2];
int x, y, value;
printf("\n\nEnter 'U' OR 'Q': ");
scanf("%s",cmd);
if(cmd[0]=='U') //Update Value
{
printf("Enter (x): ");
scanf("%d",&x);
printf("Enter (value): ");
scanf("%d",&value);
update(x, value);
}
else if(cmd[0]=='Q') //Query Summation
{
printf("Enter (x): ");
scanf("%d",&x);
value = freqTo(x);
printf("Summation from [1] to [%d]: %d",x,value);
}
else
printf("Please Type Again");
}
scanf(" ");
return 0;
}

== ตัวอย่าง Code ของ Fenwick Tree (2 มิติ) ==
/*
DATA STRUCTURE
+ 2D Fenwick Tree
+ Update(x, y, value)
:: O(lg n)
:: Add value at position[x][y]
+ FreqTo(x, y)
:: O(lg n)
:: Query summation from postion [1][1] to position[x][y]
- Memory O(max_size)
AUTHOR
+ Roos
*/
#include<stdio.h>
#define MAXSIZE 1000
int tree[MAXSIZE+1][MAXSIZE+1], n;
void update(int x, int y, int value)
{
for(int i=x; i<=MAXSIZE; i+=(i&-i))
for(int j=y; j<=MAXSIZE; j+=(j&-j))
tree[i][j] += value;
}
int freqTo(int x, int y)
{
int sum = 0;
for(int i=x; i>=1; i-=(i&-i))
for(int j=y; j>=1; j-=(j&-j))
sum += tree[i][j];
return sum;
}
int main()
{
while(1)
{
char cmd[2];
int x, y, value;
printf("\n\nEnter 'U' OR 'Q': ");
scanf("%s",cmd);
if(cmd[0]=='U') //Update Value
{
printf("Enter (x y): ");
scanf("%d%d",&x,&y);
printf("Enter (value): ");
scanf("%d",&value);
update(x, y, value);
}
else if(cmd[0]=='Q') //Query Summation
{
printf("Enter (x y): ");
scanf("%d%d",&x,&y);
value = freqTo(x, y);
printf("Summation from [1][1] to [%d][%d]: %d",x,y,value);
}
else
printf("Please Type Again");
}
scanf(" ");
return 0;
}
</syntaxhighlight>

Fenwick Tree - Revision history

Tata: Created page with "* เอามาจาก wiki.acioi.in.th '''Fenwick Tree''' หรือ '''Binary Index Tree''' * ใช้แก้ปัญหาที่ว่า "ถ้าต้อ..."