Bài tập Cây nhị phân đây (sao ko thấy ai nói về cái này hết z nhỉ)
Đề:
Cho dãy số nguyên A gồm n số (n≤100000,0≤Ai≤10000) và k phép biến đổi
Mỗi phép biến đổi thuộc 2 loại:
U u v : Cập nhật giá trị v tại phần tử thúa u của mản A.
Q u v : Tính tổng các phần tử từ u đến v của mảng A.
Input:ListQuery.inp
-Dòng đầu ghi số n,k(k≤100000).
-Dòng thứ 2 ghi n số nguyên trong dãy A.
-k dòng tiếp theo mỗi dòng ghi 1 phép biến đổi.
Output:ListQuery.out
-Mỗi dòng tương ứng với 1 kết quả tìm được của phép biến đổi Q u v
Ví dụ:
ListQuery.inp
10 7
1 2 3 4 5 6 7 8 9 10
Q 1 10
U 1 9
U 5 8
Q 1 5
Q 2 10
U 10 1
Q 10 10
ListQuery.out
55
26
57
1

Code:

program ListQuery;
const
  fi='ListQuery.inp';
  fo='ListQuery.out';
  maxN=round(1E5);
var
  a,left:array[1..maxN]of integer;
  n,k:integer;
  sum:array[1..4*maxn]of int64;
  l,h:array[1..4*maxN]of integer;
  f,g:text;
  Result:int64;


procedure Enter;
var
 i:integer;
begin
  assign(f,fi);
  reset(f);
  readln(f,n,k);
  for i:=1 to n do Read(f,a[i]);
  Readln(f);
end;

procedure Built(x:integer;low,high:integer);
var
 middle:integer;
begin
  l[x]:=low;
  h[x]:=high;
  if low=high then
  begin
      sum[x]:=a[low];
      left[low]:=x;
  end
  else
  begin
      middle:=(low+high) div 2;
      built(2*x,low,middle);
      built(2*x+1,middle+1,high);
      sum[x]:=sum[2*x]+sum[2*x+1];
  end;
end;

procedure Update(i:integer;v:integer);
var
 x:integer;
begin
  x:=left[i];
  sum[x]:=v;
  while x>1 do
  begin
      x:=x div 2;
      sum[x]:=sum[2*x]+sum[2*x+1];
  end;
end;

Function Query(i,j:integer):int64;
 Function Request(x:integer):int64;
 begin
    if (l[x]>j)or(h[x]<i) then exit(0);
    if (i<=l[x])and(h[x]<=j) then exit(sum[x]);
    Request:=Request(2*x)+Request(2*x+1);
 end;
 begin
    Query:=Request(1);
 end;

Procedure Solve;
var c:char;
    p,i,j,v:integer;
begin
  assign(g,fo);
  rewrite(g);
  for p:=1 to k do
  begin
      read(f,c);
      case c of
      'U': begin
              Readln(f,i,v);
              Update(i,v);
          end;
      'Q': begin
              Readln(f,i,j);
              WriteLn(g,Query(i,j));
          end;
      end;
  end;
end;

begin
  Enter;
  Built(1,1,n);
  Solve;
  close(f);
  close(g);
end.


Bài 2:Cho n hình chữ nhật,các hình đều có cạnh song song với trục toạ độ.Tính tổng diện tích mà các hình chữ nhật đó bao phủ
Input:Cover.inp
-Dòng 1 ghi số n(n≤10000)
-n dòng tiếp theo ghi 4 số nguyên x1,y1,x2,y2 (x1,y1,x2,y2 ≤ 10000)là toạ độ đỉnh trái trên và phải dưới của hình chữ nhật đó.
Output:Cover.out
Gồm số nguyên duy nhất là diện tích tìm đc.
(Nhớ áp dụng xây dưng cây nhị phân)

Code:

Program cover1;
uses math;
const fi='cover.inp';
      fo='cover.out';
type  bg=record
        low,high:longint;
        open:boolean;
      end;
var  f,g:text;
      labe:array[1..2*20000]of bg;
      cover,number:array[1..4*20000]of longint;
      h:array[1..2*20000]of integer;
      n,area,min1,max1:longint;

Procedure nhap;
 var i,y,z:longint;
 begin
    assign(f,fi);reset(f);
    readln(f,n);
    i:=0;
    min1:=maxlongint;
    max1:=-maxlongint;
    while i<2*n do
    begin
      i:=i+2;
      readln(f,h[i-1],y,h[i],z);
      labe[i].low:=z;
      labe[i].high:=y;
      if y>max1 then max1:=y;
      if z<min1 then min1:=z;
      labe[i-1]:=labe[i];
      labe[i-1].open:=true;
      labe[i].open:=false;
    end;
    close(f);
 end;

procedure open_true(a,b,k,low,high:longint);
 begin
    if a>=b then
    begin
    cover[k]:=0;
    exit;
    end;
    if (low<=a)and(b<=high) then
    begin
      number[k]:=number[k]+1;
      cover[k]:=b-a;
      exit;
    end;
    if (high<=a)or(b<=low) then exit;
    open_true(a,(a+b) div 2,2*k,low,high);
    open_true((a+b)div 2,b,2*k+1,low,high);
    if number[k]=0 then cover[k]:=cover[2*k]+cover[2*k+1];
 end;

 procedure open_false(a,b,k,low,high:longint);
 begin
    if a>=b then
    begin
      cover[k]:=0;
      exit;
    end;
    if (low<=a)and(b<=high) then
    begin
      number[k]:=number[k]-1;
      if number[k]=0 then cover[k]:=cover[2*k]+cover[2*k+1];
      exit;
    end;
    if (high<=a)or(b<=low) then exit;
    open_false(a,(a+b) div 2,2*k,low,high);
    open_false((a+b)div 2,b,2*k+1,low,high);
    if number[k]=0 then cover[k]:=cover[2*k]+cover[2*k+1];
 end;

 procedure sx(l,r:longint);
 var i,j,tg,x:longint;tg1:bg;
 begin
    i:=l;j:=r;
    x:=h[(i+j)div 2];
    repeat
      while h[i]<x do inc(i);
      while h[j]>x do dec(j);
      if i<=j then
      begin
          tg:=h[i];h[i]:=h[j];h[j]:=tg;
          tg1:=labe[i];labe[i]:=labe[j];labe[j]:=tg1;
          inc(i);
          dec(j);
      end;
    until i>j;
    if i<r then sx(i,r);
    if l<j then sx(l,j);
 end;

procedure xl;
var i:longint;
 begin
    sx(1,2*n);
    open_true(min1,max1,1,labe[1].low,labe[1].high);
    area:=0;
    for i:=2 to 2*n do
    begin
        area:=area+cover[1]*(h[i]-h[i-1]);
        if labe[i].open then
        open_true(min1,max1,1,labe[i].low,labe[i].high)
        else
        open_false(min1,max1,1,labe[i].low,labe[i].high);
    end;
 end;

 procedure gnkq;
 begin
    assign(g,fo);rewrite(g);
    writeln(g,area);
    close(g);
 end;

begin
  nhap;
  xl;
  gnkq;
end.