Fenwick Tree

• เอามาจาก 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 มิติ)

  1  /*
  2      DATA STRUCTURE
  3          + Fenwick Tree
  4              + Update(x, value)
  5                  :: O(lg n)
  6                  :: Add value at position[x]
  7              + FreqTo(x)
  8                  :: O(lg n)
  9                  :: Query summation from postion [1] to position[x]
 10              - Memory  O(max_size)
 11      AUTHOR
 12          + Roos
 13  */
 14  #include<stdio.h>
 15  #define MAXSIZE 1000000
 16  int tree[MAXSIZE+1], n;
 17  void update(int x, int value)
 18  {
 19      for(int i=x; i<=MAXSIZE; i+=(i&-i))
 20          tree[i] += value;
 21  }
 22  int freqTo(int x)
 23  {
 24      int sum = 0;
 25      for(int i=x; i>=1; i-=(i&-i))
 26          sum += tree[i];
 27      return sum;
 28  }
 29  int main()
 30  {
 31      while(1)
 32      {
 33          char cmd[2];
 34          int x, y, value;
 35          printf("\n\nEnter 'U' OR 'Q': ");
 36          scanf("%s",cmd);
 37          if(cmd[0]=='U')         //Update Value
 38          {
 39              printf("Enter (x): ");
 40              scanf("%d",&x);
 41              printf("Enter (value): ");
 42              scanf("%d",&value);
 43              update(x, value);
 44          }
 45          else if(cmd[0]=='Q')    //Query Summation
 46          {
 47              printf("Enter (x): ");
 48              scanf("%d",&x);
 49              value = freqTo(x);
 50              printf("Summation from [1] to [%d]: %d",x,value);
 51          }
 52          else
 53              printf("Please Type Again");
 54      }
 55      scanf(" ");
 56      return 0;
 57  }
 58 
 59 
 60 == ตัวอย่าง Code ของ Fenwick Tree (2 มิติ) ==
 61  /*
 62      DATA STRUCTURE
 63          + 2D Fenwick Tree
 64              + Update(x, y, value)
 65                  :: O(lg n)
 66                  :: Add value at position[x][y]
 67              + FreqTo(x, y)
 68                  :: O(lg n)
 69                  :: Query summation from postion [1][1] to position[x][y]
 70              - Memory  O(max_size)
 71      AUTHOR
 72          + Roos
 73  */
 74  #include<stdio.h>
 75  #define MAXSIZE 1000
 76  int tree[MAXSIZE+1][MAXSIZE+1], n;
 77  void update(int x, int y, int value)
 78  {
 79      for(int i=x; i<=MAXSIZE; i+=(i&-i))
 80          for(int j=y; j<=MAXSIZE; j+=(j&-j))
 81              tree[i][j] += value;
 82  }
 83  int freqTo(int x, int y)
 84  {
 85      int sum = 0;
 86      for(int i=x; i>=1; i-=(i&-i))
 87          for(int j=y; j>=1; j-=(j&-j))
 88              sum += tree[i][j];
 89      return sum;
 90  }
 91  int main()
 92  {
 93      while(1)
 94      {
 95          char cmd[2];
 96          int x, y, value;
 97          printf("\n\nEnter 'U' OR 'Q': ");
 98          scanf("%s",cmd);
 99          if(cmd[0]=='U')         //Update Value
100          {
101              printf("Enter (x y): ");
102              scanf("%d%d",&x,&y);
103              printf("Enter (value): ");
104              scanf("%d",&value);
105              update(x, y, value);
106          }
107          else if(cmd[0]=='Q')    //Query Summation
108          {
109              printf("Enter (x y): ");
110              scanf("%d%d",&x,&y);
111              value = freqTo(x, y);
112              printf("Summation from [1][1] to [%d][%d]: %d",x,y,value);
113          }
114          else
115              printf("Please Type Again");
116      }
117      scanf(" ");
118      return 0;
119  }