Binary Indexed Tree - Tuoitrekthc

I)                  Binary Indexed Trees.

Binary Indexed Trees thường được dùng lưu trữ các tần số và tích luỹ tần số của dữ liệu trong các bảng. Bài toán thường gặp là: có n đối tượng, cần thực hiện đáp ứng các yêu cầu sau :

(1). Yêu cầu 1: cập nhật – lấy ra, nạp vào, sửa đổi giá trị (tần số)… đối tượng i?

(2). Yêu cầu 2: Tính tổng giá trị (hoặc tần số) các đối tượng từ i tới k.

Thuật toán đáp ứng yêu cầu (1) thường có độ phức tạp thời gian là O(1), thuật toán đáp ứng  yêu cầu (2) thường có độ phức tạp thời gian là O(n). Do đó nếu có m yêu cầu dạng (2) thì thuật toán thường có độ phức tạp thời gian là O(m*n). Với m, n có kích thước lớn thì việc thực hiện thuật toán gặp trở ngại về thời gian. Sử dụng cấu trúc dữ liệu thích hợp chúng ta có thể xây dựng một thuật toán đáp ứng m yêu cầu loại (2) với độ phức tạp thời gian chỉ là O(m*logn). Cấu trúc Binary Indexed Trees là một trong những cấu trúc đáp ứng được điều này, hơn nữa viết mã nguồn đơn giản hơn và chi phí không gian bộ nhớ ít hơn so với nhiều cấu trúc dữ liệu khác.

Kí hiệu Binary Indexed Trees là BIT. Giả sử có các đối tượng i với i=1.. MaxVal, gọi f[i] là tần số xuất hiện đối tượng i, tree[i] là giá trị gắn cho nút có chỉ số i trên cây BIT. Khởi trị: f[0]=0, tree[0]=0. Xét ví dụ cho bảng tần số f ứng với các đối tượng có chỉ số i như bảng sau :

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f[i]	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2

Một số nội dung về cây BIT:

1.      Trên cây BIT nút i đại diện cho những nút nào?

(Trả lời: nút i đại diện cho những nút “hậu duệ” của nó và chính nó). Hậu duệ của nút i là những nút nào? Để trả lời cho câu hỏi này, trước hết ta viết i dưới dạng nhị phân, sau đó thay bít có giá trị 1 bên phải nhất bằng 0 (giả sử bít bằng 1 bên phải nhất là bít thứ r) ta sẽ được số j=i-2r, các nút từ j+1 đến i  là các nút do i đại diện. Không kể i, chúng được gọi là các nút “hậu duệ” của i.

Ví dụ. i=6=110(2), thì j=100(2)=4 (=6-21) -> j+1=5. Vậy nút i=6 đại diện cho các nút 5 và 6.

Nếu  i=8=1000(2) thì j=0000(2)=0, j+1=1. Vậy nút i=8 đại diện các nút từ 1 đến 8.

Nút i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Nút đại diện	1	1..2	3	1..4	5	5..6	7	1..8	9	9..10	11	9..12	13	13..14	15	1..16

Vậy hình ảnh cây BIT có thể mô tả như hình sau:

Lưu ý. Khi lập trình để tìm j=i-2r ta gán

j = i – (i & (-i)) vì  i & (-i) cho 2r

Từ hình vẽ bên nhận thấy cấu trúc cây BIT còn có thể định nghĩa đệ qui như sau :

+ Nếu nút có chỉ số i lẻ thì cha của nút i là cha[i]= i+1

+ Nếu nút có chỉ số i chẵn thì cha của nút i là cha[i]=2*cha[i div 2]

2.      Tìm tree[i] như thế nào?

Trong cài đặt cây BIT, dùng mảng tree[i] lưu tổng các tần số của các nút do i đại diện.

Ví dụ:        tree[6]=f[5]+f[6] =1+3=4,

tree[8]=f[1]+f[2]+…+f[8]=1+0+2+1+1+3+0+4=12

Hàm tạo giá trị tree[i]:

int make_node(inti){

int sum = 0;

int j=i–(i&-i)+1;//Các nút do i đại diện là các nút từ i-2r+1 đến i

while (j++<=i)  sum += f[i];

return sum;

}

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f(i)	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2
tree(i)	1	1	2	4	1	4	0	12	2	7	2	11	3	4	0	29

Kết quả:

3.      Tính C[i] lưu tổng giá trị tích luỹ trên các nút từ nút 1 đến nút i như thế nào?

Trong cài đặt cây BIT để lưu các giá trị trên các nút, người ta chỉ dùng mảng C lưu kết quả cộng dồn các giá trị tree gán trên các nút đại diện cao nhất có chỉ số không vượt quá i. Ví dụ:

C[16] = tree[16]=29

C[15]=tree[15]+tree[14]+tree[12]+tree[8]

=0+4+11+12=27

C[14]=tree[14]+tree[12]+tree[8]

=4+11+12=27

C[13]=tree[13]+tree[12]+tree[8]

=3+11+12=26…

Trong hình vẽ bên, mỗi nút thể hiện bởi một hình chữ nhật (phần trên màu xám, phần dưới trắng), chiếu hình chữ nhật biểu diễn nút sang cột chỉ số (cột bên phải hình vẽ) sẽ nhận ra chỉ số các nút được nút này đại diện). Khi chiếu, hình chữ nhật nào có hình chiếu bao trùm các hình chiếu của hình chữ nhật khác thì nút tương ứng là nút đại diện cao nhất cho các nút của các hình chữ nhật bị bao trùm. Để tìm các nút đại diện cao nhất có chỉ số không vượt quá i, ta chuyển dần từ i về các nút i -= (i & -i)

Ví dụ:

C[11]=tree[8]+tree[10]+tree[11]

=12+7+2=21

Hàm tính C[i] (i là chỉ số của nút) như sau:

int calcul_c(int i){

     int sum = 0;

     while (i > 0){

       sum += tree[i];

i -= (i & -i); //đến nút đại diện (iteration) tiếp theo

      }

     return sum;

}

Kết quả cho bảng giá trị của c[i] sau đây:

I	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f[i]	0	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2
tree[i]	0	1	1	2	4	1	4	0	12	2	7	2	11	3	4	0	29
c[i]	0	1	1	3	4	5	8	8	12	14	19	21	23	26	27	27	29

4.      Cập nhật giá trị tại một nút như thế nào? (trả lời yêu cầu 1).

Khi tăng thêm giá trị Val cho nút i thì phải cập nhật lại tất cả các nút đại diện (iteration) có chứa nút i cũng được thêm lượng Val (nghĩa là các nút cha, ông, …, tổ tiên của i cũng được cập nhật).

Ví dụ. Cập nhật lại nút i=5 (giá trị cũ là 0, giá trị mới là 1) phải cập nhật các nút j=6, 8, 16, … (xem hình vẽ ở trang trước). Có thể tìm các nút đại diện chứa i bằng quá trình ngược lại với quá trình tìm các hậu duệ của i. Nút j đại diện gần i nhất là j=i+(i & -i), sau đó lại tìm nút đại diện gần nhất của nút j, …

Chỉ số nút i	Vị trí bit 1bên phảinhất	i & -i	Nút đại diệncho i làj=i+( i & -i)
i=5 = 101	0	120=1	5+1=6
i=6 = 110	1	21=2	6+2=8
i=8 = 1000	3	23=8	8+8=16
i=16 = 10000	4	24=16	16+16=32
i=32 = 100000	…	…	…

Chương trình con cập nhật lại cây BIT khi nút i thêm giá trị là Val:

void update(int i ,int val){

     while (i <= MaxVal){

                 tree[i] += val;

                 i += (i&-i); // đến các nút tiền bối (cha, ông, …tổ tiên…MaxVal) của  i

     }

}

5.      Tìm lại tần số ứng với một nút như thế nào

Khi đã biết mảng C chứa tổng do cộng tích luỹ các tần số tại từng nút? Chúng ta có thể chứng minh f[i]=C[i]-C[i-1] (1) với mọi i=1, 2, …MaxVal. Dựa vào công thức này suy ra cách tính f[i] dựa vào các giá trị đã gắn trên các nút của cây BIT: Thật vậy C[i] và C[i-1] là hai tổng tích lũy của các giá trị gán trên các nút từ nút i và i-1 đi về nút 1; trên hai đường đi này có chung nhiều nút nên ta chỉ cần tính f[i] bằng cách trừ dần tree[i] cho các tree[j] thuộc tổng C[i] mà không thuộc tổng C[i-1]. Các số j này nằm ở những vị trí trong khoảng giữa z+1=i-(i & -i)+1 và i. Với mỗi giá trị j ta lại lặp lại cách thức trên.

Ví dụ:  i= 12;  z= i–(i&-i) = 8, nên j=trong khoảng i-1 đi về 8 là 11 và 10.

Thật vậy: C[12]= tree[12]+tree[8], C[11]=tree[11]+ tree[10]+tree[8] nên có:

f[12]=C[12]-C[11]=(tree[12]+tree[8])-(tree[11]+ tree[10]+tree[8])=

tree[12]-tree[11]-tree[10]=11-2-7=2.

int GiveF(int i){ //Hàm trả về  f[i]

int sum = tree[i];

if (i > 0){

    int z = i – (i & -i);

    i–;

    while (i != z){//các số i mới đóng vai trò j

           sum -= tree[i];

           i -= (i & -i);//Lặp lại với j

    }

}

return sum;

}

6.      Cho một giá trị là value, cách tìm chỉ số i sao cho tree[i] bằng value?

Chúng ta áp dụng tìm kiếm nhị phân.

int find(int value){

       int i = 0; j = n; //n là số lượng đối tượng (số nút trên cây), j điểm chia              

   while ((j != 0) && (i < MaxVal)){

         int k = i + j;

         if (value == tree[k])  return k;

         else if (value > tree[k]){

               i = k;

               value -= tree[k];

         }

         j >>= 1;

   }

   if (value == 0) return -1;

   else  return i;

}

7.      Tính tổng các giá trị được tích luỹ từ nút i đến nút j (kể cả tích luỹ trên nút i và trên nút j)như thế nào? (trả lời yêu cầu 2).

Rõ ràng tổng các giá trị được tích luỹ từ nút i đến nút j (i<=j) bằng tổng tích luỹ đến nút j trừ đi các giá trị đã tích luỹ trên các nút trước i (đó là tổng các giá trị được tích luỹ trên nút i-1). Ta có hàm tính tổng này như sau:

int sum(int i, int j) {

       return calcul_c(j)- calcul_c(i-1);

} 

8.      Bài toán ứng dụng.

Có dãy N tấm bìa. Các tấm bìa đều úp mặt trên bàn. Bạn có hai câu chất vấn cần thực hiện:

1. T i j là đề nghị quay ngược các tấm bìa từ chỉ số i đến chỉ số j (kể cả i và j) tấm nào đang úp thì thành ngửa, tấm nào đang ngửa thì úp xuống
2. Q i yêu cầu trả lời là 0 nếu tấm bìa i là úp, ngược lại trả lời là 1 nếu tấm bìa i ngửa.

Input. Tệp gồm nhiều dòng, mỗi dòng là một chất vấn thuộc hai loại trên

Output. Gồm một số dòng, mỗi dòng là một trả lời cho chất vấn Q(i), theo đúng thứ tự chất vấn trong input.

Ví dụ.

input	output
T 1 4T 3 6T 2 5Q 1Q 2 Q 3 Q 4 T 2 3 Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7	10111 1 0 1 0 1 0

Hướng dẫn. Ban đầu các bìa chưa chịu tác động nào nên coi tần số các nút đều bằng 0. Giá trị tích luỹ tổng các tần số lên các nút cũng bằng 0 tại mọi nút. Thực hiện chất vấn T(i, j): với mỗi nút k nằm giữa i và j (kể cả i và j) cần cập nhật tree[k] thêm 1 (vì thêm một lần lật quân k). Câu trả lời cho Q(i) chính là f[i] mod 2 (vì ban đầu i úp, sau số chẵn lần lật thì vẫn úp). Lời giải cho mỗi câu chất vấn được thực hiện trong thời gian O(logN).

II) Cấu trúc Binary indexed trees 2-D.

Cấu trúc Binary Indexed Trees tổ chức trên  mảng một chiều có thể tổng quát hoá thành cấu trúc Binary Indexed Trees trên mảng nhiều chiều. Sau đây là cấu trúc Binary Indexed Trees trên mảng hai chiều (2-Dimensions).

Xét mảng hai chiều kích thước A[1..M, 1..N] (M dòng, N cột), giả sử đánh số hàng từ 1 đến M và đánh số cột từ 1 đến N. Ta xây dựng tập S1 gồm M cây BIT (Binary indexed trees), mỗi BIT dùng xử lý thông tin một dòng của mảng A  (mỗi BIT có N nút, mỗi nút i gán giá trị là tổng tích luỹ từ ô 1 đến ô i của dòng). Đồng thời xây dựng tập S2 gồm N cây BIT: cây BIT thứ nhất của S2 quản lý các nút thứ nhất của M cây BIT thuộc S1, cây BIT thứ hai của S2 quản lý các nút thứ hai của M cây BIT thuộc S1, …, cây BIT thứ N của S2 quản lý các nút thứ N của M cây BIT thuộc S1.

1.      Cập nhật nút (x;y)

Khi cần cập nhật thêm giá trị amount vào ô (x;y) thuộc dòng y cột x của mảng A ta cập nhật lại các ô là tiền bối của (x;y) như sau:

1. a) Trên cây BIT thứ y của tập S1, tìm các nút xtiền bối của nút x
2. b) Với mỗi cây BIT thứ xtiền bối của tập S2, tìm các nút ytiền bối của y.

Cập nhật ô (xtiền bối; ytiền bối).

void update (int x, int y, int amount){

  int ix, jy;

for( ix=x; ix < maxM; ix += (ix & (-ix)) ) // Tìm đến các tiền bối của x 

for( jy=y; jy < maxN; jy += (jy & (-jy)) // Tìm đến các tiền bối của y

     A[jy][ix] += amount; // Cập nhật các ô tiền bối của ô (x,y) dòng y, cột x

}

Hai hình sau đây lần lượt minh hoạ cập nhật ô (1; 1) và ô (2; 5) dòng 5, cột 2

Cập nhật ô [1; 1]	Cập nhật ô [5; 2]
Chú ý : Trong mỗi cây BIT, nút 8 là cha của nút 4, 6 và 7 ; nút 4 là cha của nút 2 và 3; nút 2 là cha của nút 1; nút 6 là cha của nút 5

2.      Tính tổng các ô trong hình chữ nhật (x1, y1,x2,y2)

Để trả về tổng các ô trong hình chữ nhật có góc trái-dưới là ô (x1;  y1) và góc phải-trên là ô (x2; y2) ta thực hiện quá trình ngược lại quá trình cập nhật:

1. a) Trên cây BIT thứ x2 của S1, tìm các jy là các hậu duệ của y2, jy>y1
2. b) Trên cây BIT thứ jy của S2, tìm các ix là các hậu duệ của x2, ix>x1
3. c) Giảm tổng tích luỹ trên (x2; y2) một lượng là tổng tích luỹ trên các ô hậu duệ (ix; jy).

Hàm tính tổng các ô trong hình chữ nhật có góc trái-dưới là ô (x1; y1) và góc phải-trên là ô (x2; y2) giới thiệu trong ví dụ dưới đây:

3.      Ví dụ.  Giải bài tập MATSUM – Matrix Summation

Cho ma trận A (N × N) các số. BuggyD là nhà phân tích ma trận và anh ấy muốn biết tổng các số trong một ma trận con bất kỳ của A, do đó muốn có một hệ thống cho kết quả ứng với các truy vấn này. Hệ thống cũng đáp ứng ngay cả khi ma trận biến động chấp nhận các giá trị mới trên các ô của ma trận. Giả sử ban đầu các ô của ma trận đều bằng 0. Bạn hãy xây dựng hệ thống cho BuggyD. Đọc khuôn dạng input cho chi tiết dưới đây

Input

Dòng đầu tiên của input chứa số nguyên t, là số các test. Tiếp theo là t test. Dòng đầu của mỗi test chứa số nguyên N (1 <= N <= 1024), là chiều rộng ma trận. Tiếp theo là danh sách các lệnh, mỗi lệnh có một trong 3 dạng sau:

SET x y num – Đặt giá trị tại ô (x, y) (0 <= x, y < N) thành num

SUM x1 y1 x2 y2 – Tìm và xuất ra tổng các số trong hình chữ nhật từ ô (x1, y1) đến ô (x2, y2), kể cả chúng, x1 <= x2 và y1 <= y2, và kết quả không vượt quá số nguyên 32 bit.

END – Kết thúc một test.

Output

Với mỗi test, output trên một dòng cho mỗi lệnh SUM. Để một dòng trống sau mỗi test.

Ví dụ

Input:

1

4

SET 0 0 1

SUM 0 0 3 3

SET 2 2 12

SUM 2 2 2 2

SUM 2 2 3 3

SUM 0 0 2 2

END

Output

1

12

12

13

Chương trình.

#include <iostream>

#include <fstream>

using namespace std;

#define LL long long

LL tree[1050][1050];

void update(int x,int y,int val,int MAX){

    while(x<=MAX)    {

        int ty = y;

        while(ty <= MAX)        {

            tree[x][ty] += val;

            ty += (ty & -ty);

        }

        x += (x & -x);

    }

}

LL read(int x,int y){  //Tổng các số trong hcn từ (0,0) đến (x-1, y-1)

    LL sum = 0;

    while( x )    {

        int ty = y;

        while( ty )        {

            sum += tree[x][ty];

            ty -= (ty & -ty);

        }

        x -= (x & -x);

    }

    return sum;

}

int main(){

    int t;

    freopen(“matsum.inp”,”r”,stdin);

    freopen(“matsum.out”,”w”,stdout);

    scanf(“%d”,&t);

    while(t–) {

        int n;

        scanf(“%d”,&n);

        memset(tree,0,sizeof tree);

        while(1) {

            char s[10];

            scanf(“%s”,s);

            if(s[1] == ‘E’){ //SET

                int x,y,val;

                scanf(” %d%d%d”,&x,&y,&val);//Yêu cầu đặt giá trị tại ô (x,y)thành val

                                       //Giá trị đã có tại ô (x,y)

                LL p_val=read(x+1,y+1)+read(x,y)-read(x+1,y)-read(x,y+1);

                update(x+1,y+1,val-p_val,n+9); // Thêm val-p_val vào ô (x,y)

            }

            else if(s[1] == ‘U’){ //SUM

                LL sum = 0;

                int x1,y1,x,y;

                scanf(” %d%d%d%d”,&x,&y,&x1,&y1); //Xuất ra tổngtrong hcn(x,y,x1,y1)

                sum=read(x1+1,y1+1)+read(x,y)-read(x,y1+1)-read(x1+1,y);

                printf(“%lld\n”,sum);

            }

            else{

                //printf(“\n”);

                break;

            }

        }

        printf(“\n”);

    }

    return 0;

}

Ghi chú.

read(x1+1,y1+1): cho tổng các số trong hcn OEBF

read(x,y): cho tổng các số trong hcn OHDK

read(x,y1+1): cho tổng các số trong hcn OEAK

read(x1+1,y); cho tổng các số trong hcn OHCF

Do đó: read(x1+1,y1+1)+read(x,y)-read(x,y1+1)-read(x1+1,y); cho tổng các số trong hcn ABCD

4. Bài toán ứng dụng.

Giả thiết một thế hệ thứ 4 điện thoại di động (mobile phone) có các trạm làm việc nằm trong vùng Tampere hoạt động như sau: Vùng hoạt động này được chia theo lưới ô vuông. Các ô vuông tạo thành một ma trận SxS với các hàng và cột được đánh số từ 0 đến S-1. Mỗi ô vuông chứa một trạm làm việc. Số lượng các điện thoại đang hoạt động trong một ô vuông sẽ bị thay đổi khi người sử dụng điện thoại di chuyển từ ô này sang ô khác hoặc điện thoại chuyển chế độ bật/tắt. Theo thời gian, mỗi trạm làm việc sẽ báo cáo sự thay đổi số lượng điện thoại di động đang hoạt động trong khu vực kiểm soát của mình.

Hãy viết chương trình nhận các báo cáo đó và trả lời được các yêu cầu về tổng số điện thoại di động đang hoạt động trong một vùng không gian hình vuông cho trước. Hãy viết chương trình  tiếp nhận các báo cáo này và trả lời các yêu câu cho biết tổng số điện thoại đang hoạt động trong một hình chữ nhật của vùng.

Input: Dữ liệu vào đọc từ tệp input chuẩn như các số nguyên và trả lời các chất vấn ghi vào output chuẩn như các số nguyên. Dữ liệu vào đã được mã hoá như sau: Mỗi dữ liệu vào trên một dòng riêng gồm một số nguyên chỉ dẫn và một số tham số nguyên như bảng sau:

Số nguyên chỉ dẫn	Các số nguyên tham số	Ý nghĩa
0	S	Khởi trị ma trận kích thước SS. Chỉ dẫn này chỉ cho một lần và là chỉ dẫn đầu tiên
1	X Y A	Thêm A điện thoại hoạt động trong trạm (x,y)
2	L B R T	Hỏi tổng số điện thoại đang hoạt động trong các trạm (x,y) với L≤x≤R, B≤y≤T.
3	Dừng chương trình. Chỉ dẫn này chỉ cho một lần và là chỉ dẫn cuối cùng.

Các giá trị luôn trong phạm vi, không cần kiểm tra. Riêng A có thể âm, khi đó không giảm giá trị trạm xuồng dưới 0. Các chỉ số bắt đầu từ 0 ví dụ bảng 44 thì có 0 x3, 0y3. Chương trình của bạn sẽ không trả lời cho bất kì chỉ dẫn nào khác 2. Nếu chỉ dẫn là 2 thì chương trình của bạn cần trả lời chất vấn bằng ghi trả lời trên đúng một dòng chứa số nguyên trên tệp output.

Stdin(input chuẩn)	Stdout(output chuẩn)	Giải thích
0 4	Khởi trị bảng 4´4
1 1 2 3	Cập nhật bảng tại ô (1,2) với +3
2 0 0 2 2	Chất vấn tổng trong hình chữ nhật gồm các ô (x,y) mà 0≤x≤2; 0≤y≤2
3	Trả lời chất vấn
1 1 1 2	Cập nhật bảng tại ô (1,1) với +2
1 1 2 -1	Cập nhật bảng tại ô (1,2) với -1
2 1 1 2 3	Chất vấn tổng trong hình chữ nhật gồm các ô (x,y) mà 1≤x≤2; 1≤y≤3
4	Trả lời chất vấn
3	Dừng chương trình

Hạn chế:

Kích thước bảng	S´S	1´1 ≤ S´S ≤ 1024´1024
Giá trị mỗi ô là V tại bất kì thời điểm nào	V	0 ≤ V  ≤ 215-1 (=32767)
Lượng cập nhật	A	-215  ≤ A  ≤ 215-1
Số lượng chỉ dẫn trong input	U	3  ≤ U  ≤ 60002
Số tối đa điện thoại trong bảng	M	M=230

Trong 20 test input có 16 test kích thước bảng tối đa là 512.

Hướng dẫn. Xây dựng cây BIT_2D. Lưu ý, trong các cây BIT thuộc tập S1 và tập S2, các nút được đánh số từ 1 đến N, nhưng trong bài toán này dòng và cột của mảng đánh số từ 0.

 

 

 

 

 

 

 

Chia sẻ:

• X
• Facebook

Thích Đang tải...