1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
typedef struct{
    int x,y;
}point;
#define MAX_SIZE (2<<20)
int generation[19] = { 2, 3, 6, 12,
                     24, 48, 96, 192, 384,
                    768, 1536, 3072, 6144, 12288,
                    24576, 49152, 98304, 196608, 393216};
point btree[MAX_SIZE];
void init_btree(int height,int location,int x,int y){
    btree[location].x = x;
    btree[location].y = y;
    if(height > 1){
        init_btree(height-1,location*2,x+generation[height-2],y-generation[height-2]);
        init_btree(height-1,location*2+1,x+generation[height-2],y+generation[height-2]);
    }
}
int count_sum_ofarea(int location,int x1,int y1,int x2,int y2,int height){
    if(height == 0) return 0;
    if(btree[location].x>x2) return 0;
    int sum = 0;
    if(x1 <= btree[location].x && btree[location].x <= x2 &&
       y1 <= btree[location].y && btree[location].y <= y2){
        sum++;
       }
    if(btree[location].y < y2){
        sum += count_sum_ofarea(location*2+1,x1,y1,x2,y2,height-1);
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX