pku1195 Mobile phones

需要一个这样的数据结构，每次能修改矩阵中的某一个值，还可以查询某个子矩阵的权值和。

二维树状数组没压力啊。

View Code

 1 program pku1195(input,output);
 2 var
 3    c      : array[0..1500,0..1500] of int64;
 4    n,kk : longint;
 5 function lowbit(x: longint ):longint;
 6 begin
 7    exit(x and (-x));
 8 end; { lowbit }
 9 procedure insect(x,y,w :longint );
10 var
11    k : longint;
12 begin
13    while x<=n do
14    begin
15       k:=y;
16       while k<=n do
17       begin
18      inc(c[x,k],w);
19      k:=k+lowbit(k);
20       end;
21       x:=x+lowbit(x);
22    end;
23 end; { insect }
24 function find(x,y :longint ):longint;
25 var
26    k : longint;
27 begin
28    find:=0;
29    while x>0 do
30    begin
31       k:=y;
32       while k>0 do
33       begin
34      inc(find,c[x,k]);
35      k:=k-lowbit(k);
36       end;
37       x:=x-lowbit(x);
38    end;
39 end; { find }
40 procedure main;
41 var
42    x1,y1,x2,y2 : longint;
43 begin
44    read(kk);
45    while kk<>3 do
46    begin
47       case kk of
48     0 : begin
49            readln(n);
50            fillchar(c,sizeof(c),0);
51         end;
52     1 : begin
53            readln(x1,y1,x2);
54            inc(x1);
55            inc(y1);
56            insect(x1,y1,x2);
57         end;
58     2 : begin
59            readln(x1,y1,x2,y2);
60            inc(x1); inc(y1);
61            inc(x2); inc(y2);
62            writeln(find(x2,y2)+find(x1-1,y1-1)-find(x2,y1-1)-find(x1-1,y2));
63         end;
64       end; { case }
65       read(kk);
66    end;
67 end;
68 begin
69    main;
70 end.