Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)

Giới thiệu về cây Fenwick (hay còn được gọi là BIT)
BIT-yeulaptrinh.pw

Tổng quát, đặt m = 2k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong Fenwick-Tree, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2k nút có số hiệu từ m- 2k+1 đến m.

Ví dụ:

    – 8 = 23.1, vậy 8 là nút gốc của các nút 1, 2, 3, …, 8.

    – 12 = 22.3, vậy 12 là nút gốc của các nút  9, 10, 11, 12

    – 10 = 21.5, vậy 10 là nút gốc của các nút  9, 10.

    – 7 = 20.7, vậy 7 là nút gốc của chỉ nút  7.

    – 16 = 24.1, vậy 16 là nút gốc của các nút 1, 2, 3, …, 16.

Trong Fenwick-Tree, nút gốc đại diện cho tất cả các nút con của nó. Ý nghĩa của từ đại diện ở đây thường dùng là nút gốc lưu tổng giá trị của các nút con. Vì vậy khi tính toán, ta chỉ cần truy xuất nút gốc là đủ mà không cần thiết phải truy xuất đến các nút con. Xét ví dụ:

       Cho mảng gồm n phần tử a1, a2, …, an. Hãy tính tổng Am =  a1 + a2 + … + am (m ≤ n).

Thay vì sử dụng vòng lặp từ 1 đến m để truy xuất từng phần tử ai một (độ phức tạp O(m)), ta sử dụng cấu trúc FENWICK-TREE như sau:

    – t1 = a1

    – t2 = a1 + a2

    – t3 = a3

    – t4 = a1 + a2 + a3 + a4

    – t5 = a5

    – t6 = a5 + a6

    – t7 = a7

    – t8 = a1 + a2 + a3 + a4+ a5 + a6 + a7 + a8

    – …

    – t12 = a9 + a10 + a11 + a12

    – … (tiếp tục như vậy theo cách xây dựng Fenwick-Tree)

 

    * Để tính A15 (m=15), thay vì phải duyệt từ a1 đến a15, ta chỉ cần tính t8 + t12 + t14 + t15 .

    * Để tính A10, chỉ cần tính t8 + t10

    * Để tính A13, chỉ cần tính t8 + t12 + t13

    * Để tính A16, lấy ngay giá trị t16

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, sau đó lần lượt xóa các bít 1 của m theo thứ tự từ phải sang trái, tại mỗi bước trung gian chính là chỉ số nút cần truy xuất trong Fenwick-Tree.

Ví dụ: m = 13 có biểu diễn nhị phân là 1101:

     1) 1101 -> truy xuất nút 13

     2) Xóa bít 1 bên phải nhất còn 1100 -> truy xuất nút 12

     3) Xóa bít 1 bên phải nhất còn 1000 -> truy xuất nút 8

     4) Xóa bít 1 bên phải nhất và dừng.

Thao tác truy xuất các nút như trên được gọi là getFENWICK-TREE. May mắn là ta có một công thức rất đơn giản để xóa bít 1 bên phải dùng phép toán AND. Thủ tục getFENWICK-TREE như sau:

int getFENWICK-TREE(int m)
{
            int result = 0;
            for(; m> 0; m &= m-1
            {
                        result += t[m];
            }
            return result;
}

Độ phức tạp của getFENWICK-TREE là O(log2m)

Vấn đề còn lại là làm thế nào để xây dựng được Fenwick-Tree như trên? Cách thực hiện là ban đầu khởi tạo các nút của Fenwick-Tree là 0. Sau đó ứng với mỗi giá trị am thì cập nhật các nút cha liên quan trong cây. Ví dụ:

    – Cập nhật giá trị a5 -> cần cập nhật các nút t5, nút cha t6, nút cha t8, nút cha t16,….

    – Cập nhật giá trị a9 -> cần cập nhật các nút t9, nút cha t10, nút cha t12, nút cha t16,…

    – Cập nhật giá trị a4 -> cần cập nhật các nút t4, nút cha t8, nút cha t16,…

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, nếu cộng 1 vào bít bên phải nhất của m thì ta được nút cha của m.

Ví dụ, m = 5 có biểu diễn nhị phân là 101:

    1) 101 -> cập nhật nút 5

    2) Cộng 1 vào bít phải nhất thành 0110 -> cập nhật nút 6

    3) Cộng 1 vào bít phải nhất thành 1000 -> cập nhật nút 8

    4) Cộng 1 vào bít phải nhất thành 10000 -> cập nhật nút 16.

Thao tác cập nhật các nút từ con đến cha như trên được gọi là updateFENWICK-TREE. Ta cũng có một công thức rất đơn giản để cộng 1 vào bít 1 bên phải nhất dùng phép toán AND. Thủ tục updateFENWICK-TREE như sau:

void updateFENWICK-TREE(int m, int value)
{
   for(; m<= n; m += m & -m)
   {
        t[m] += value;
   }
}

Độ phức tạp của updateFENWICK-TREE là O(log2n)

Trên đây là lý thuyết về Binary Indexed Tree. Bây giờ ta sẽ áp dụng FENWICK-TREE để giải bài Dãy nghịch thế và Dĩa nhạc 3.

Dãy nghịch thế: (Theo cách vét cạn thì cần xét tất cả các cặp, độ phức tạp là O(n2))

Phác thảo thuật toán:

– Dùng một mảng đếm t[100.000], t[u] cho biết hiện giờ có bao nhiêu số nhỏ hơn u.

– Đầu tiên khởi tạo các phần tử mảng t là 0.

– Duyệt từ cuối mảng lên đầu mảng (i từ n->1), ứng với mỗi ai thực hiện hai thao tác:

    1) Kiểm tra xem hiện giờ có bao nhiêu số nhỏ hơn ai (truy xuất t[ai]).

    2) Cập nhật ai vào mảng t, nghĩa là tăng các phần tử từ t[ai+1] đến t[100.000], mỗi phần tử thêm 1.

Tuy nhiên trong thao tác 2 việc cập nhật như vậy tổng thể độ phức tạp vẫn là O(n2). Bây giờ ta sẽ chuyển mảng t thành cấu trúc FENWICK-TREE. Đối với thao tác 1 dùng getFENWICK-TREE, đối với thao tác 2 dùng updateFENWICK-TREE.

Chương trình hoàn chỉnh

cin>>n;
for(i= 1; i<= n; i++) cin>>a[i];
kq = 0;
for(i= n; i>= 1; i–)
{
            kq += getFENWICK-TREE(a[i]);
            updateFENWICK-TREE(a[i]+1, 1);
}
cout<<kq;

Độ phức tạp là O(nlog2n)

PVOI14_4 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

Uses    math;
const   fi      ='';
        fo      ='';
        maxN    =5*trunc(1e4)+1;
 
type    arr1    =array[0..maxN] of longint;
        arr2    =array[0..maxN,1..4] of longint;
 
var     n       :longint;
        a       :arr1;
        T       :arr2;
        cs      :arr1;
        f       :arr2;
procedure QS(var a,cs:arr1;l,r:longint);
var     i,j,x,tg        :longint;
begin
        i:=l;j:=r;
        x:=a[l+random(r-l+1)];
        repeat
                while a[i]<x do inc(i);
                while a[j]>x do dec(j);
                if i<=j then
                begin
                        tg:=a[i];a[i]:=a[j];a[j]:=tg;
                        tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if l<j then QS(a,cs,l,j);
        if i<r then QS(a,cs,i,r);
end;
 
Procedure Update(x,k,v:longint);
begin
        while x<=maxN do
        begin
                T[x,k]:=max(T[x,k],v);
                x:=x+x and (-x);
        end;
end;
 
function Get(x,k:longint):longint;
begin
        Get:=0;
        while x>0 do
        begin
                Get:=Max(Get,t[x,k]);
                x:=x-x and (-x);
        end;
end;
 
procedure xuly;
var     i, j    :longint;
        a2 :arr1;
        dem     :longint;
        max_h   :longint;
        tmp     :longint;
        ans     :longint;
begin
        for i:=1 to n do a2[i]:=a[i];
        fillchar(t,sizeof(t),0);
        QS(a2,cs,1,n);
        dem:=1;
        a[cs[1]]:=dem;
        for i:=2 to n do
                begin
                        if a2[i]>a2[i-1] then inc(dem);
                        a[cs[i]]:=dem;
                end;
        //for i:=1 to n do write(a2[i],' ');writeln;
        max_h:=dem;
        ///// 1
        for i:=1 to n do
                begin
                        f[i,1]:=Get(a[i]-1,1)+1;
                        Update(a[i],1,f[i,1]);
                end;
        ///2
        for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],2)+1;
                        if tmp<=2 then tmp:=0;
                        begin
                                f[i,2]:=tmp;
                                Update(max_h-a[i]+1,2,max(f[i,1],f[i,2]));
                        end;
                end;
       // writeln(f[5,2]);
        ///3
         for i:=1 to n do
                begin
                        tmp:=Get(a[i]-1,3)+1;
                        if tmp<=3 then tmp:=0;
 
                        begin
                                f[i,3]:=tmp;
                                Update(a[i],3,max(f[i,2],f[i,3]));
                        end;
                end;
         //writeln(f[11,3]);
         //4
          for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],4)+1;
                        if tmp<=4 then tmp:=0;
 
                        begin
                                f[i,4]:=tmp;
                                Update(max_h-a[i]+1,4,max(f[i,3],f[i,4]));
                        end;
                end;
         // writeln(f[14,4]);
          ans:=0;
          for i:=1 to n do ans:=max(ans,f[i,4]);
          writeln(ans);
end;
procedure run;
var     i :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        cs[i]:=i;
                end;
        xuly;
        close(input);close(output);
end;
 
begin
        run;
end.

NTSEQ – spoj

Đề bài: http://vn.spoj.com/problems/NTSEQ/

Thuật toán:

  • Rời rạc hóa rồi sử dụng cấu trúc dữ liệu BIT để tính
  • Các bạn mới học cần phải làm bài này trước mới hiểu rõ được: http://yeulaptrinh.pw/102/lis-va-liq-su-dung-bit-spoj/
  • Mỗi nút của cây BIT lưu 2 giá trị là số lượng và độ dài dãy con dài nhất
  • Đọc code các bạn có thể hiểu ngay được

Code:

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e5;
const int INF = 1e9 + 7;
 
int n, a[MAXN], b[MAXN], __max = 0;
int f[MAXN];
 
struct data{
    int val, sl;
} T[MAXN];
 
void add(int &a, int b)
{
    a += b;
    if (a > INF) a -= INF;
}
 
data get(int x)
{
    data ans; ans.val = 0; ans.sl = 0;
    for(int i = x; i > 0; i -= i & -i) {
        if (ans.val < T[i].val) ans = T[i];
        else if (ans.val == T[i].val) add(ans.sl, T[i].sl);
    }
    return ans;
}
 
void update(int x, int val, int sl)
{
    for(int i = x; i <= __max + 1; i += i & -i){
        if (val > T[i].val) T[i].val = val, T[i].sl = sl;
        else {
                if (val == T[i].val) add(T[i].sl, sl);
        }
    }
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    FORE(i, 1, n) cin >> a[i];
    FORE(i, 1, n) b[i] = a[i]; sort(b + 1, b + n + 1);
    FORE(i, 1, n) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    __max = *max_element(a + 1, a + n + 1);
    a[n + 1] = __max + 1;
    FORE(i, 1, n + 1){
        data tmp = get(a[i] - 1);
        f[i] = tmp.val + 1;
        if (tmp.sl == 0) tmp.sl++;
        if (i == n + 1) cout<<tmp.sl<<endl;
        update(a[i], f[i], tmp.sl);
    }
	return 0;
}

C11SEQ – spoj

Đề bài: http://vn.spoj.com/problems/C11SEQ/

Thuật toán:

  • Gọi S[i] là tổng từ a[1] đến a[i]
  • Ta biến đổi yêu cầu đề bài
    • <span class="coMULTI">L &lt;= a[i] + a[i+1] + ... + a[j] &lt;= R</span>
    • <span class="coMULTI">=&gt;    L&lt;=s[i] - s[j-1]&lt;=R</span>
    • =>        s[j-1]>=s[i]-r;
                   s[j-1]<=s[i]-l;
  • Lưu các giá trị s[i] – r và s[i] – l và mảng kt 2*n ——> rời rạc hóa thành mảng b[1..2*n] ——> lưa vào cây BIT để tính:
    <span class="st0">ans := ans + get(b[i]) - get(b[n+i]);</span>

Code:

const
  fi='';//c11seq.inp';
  fo='';//c11seq.out';
  maxn=trunc(1e5);
var
  s,sr,sl : array[0..maxn] of int64;
  a  : array[0..maxn*3] of int64;
  b,cs,t  : array[0..maxn*3] of longint;
  i,j,n,l,r : longint;
  ans : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n,l,r);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do if (l<=a[i]) and (r>=a[i]) then inc(ans);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint);
  var i,j : longint;
      x : int64;
  begin
    i :=l;j:=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]<x do inc(i);
      while a[cs[j]]>x do dec(j);
      if i<=j then
        begin
          swap(cs[i],cs[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
  end;
procedure init;
  var i,hold : longint;
  begin
    for i := 1 to n do s[i] := s[i-1] + a[i];
    for i := 1 to n do sl[i] := s[i] - l;
    for i := 1 to n do sr[i] := s[i] - r - 1;
    for i := 1 to n do
      begin
        a[i] := sl[i];
        a[n+i] := sr[i];
        a[n+n+i] := s[i-1];
      end;
    //a[2*n+1] := s[0] - l;
    //a[2*n+2] := s[0] - r;
    for i:=1 to 3*n do cs[i] := i;
    qs(1,3*n);
    b[cs[1]] := 1; hold := 1;
    for i:=2 to n*3 do
      if a[cs[i]] = a[cs[i-1]] then
        begin
          b[cs[i]] := hold;
        end
        else
        begin
          inc(hold);
          b[cs[i]] := hold;
        end;
  end;
procedure update(i : longint);
  begin
    while i<=3*n do
      begin
        t[i] := t[i] + 1;
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  begin
    get := 0;
    while i>0 do
      begin
        get := get + t[i];
        i := i - i and (-i);
      end;
  end;
procedure process;
  var i : longint;
  begin
    for i:=1 to n do
      begin
        ans := ans + get(b[i]) - get(b[n+i]);
        update(b[2*n+i]);
      end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(Output);
    writeln(ans);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

KQUERY – SPOJ

Đề bài: http://vn.spoj.com/problems/KQUERY/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi      ='';
        fo      ='';
        maxN    =300000;
        maxQ    =2*trunc(1e5);
 
type    arr1    =array[1..maxN] of longint;
var     n, q    :longint;
        a, csa  :arr1;
        x,y,k,csk,pos,kq   :arr1;
        T       :arr1;
 
Procedure hv(var a,b:longint);
var     tg      :longint;
begin
        tg:=a;a:=b;b:=tg;
end;
 
Procedure QS1(l,r:longint);
var     i, j, tg, xx    :longint;
begin
        i:=l;
        j:=r;
        xx:=a[(i+j) div 2];
        repeat
                while a[i]<xx do inc(i);
                while a[j]>xx do dec(j);
                if i<=j then
                        begin
                                hv(a[i],a[j]);
                                hv(csa[i],csa[j]);
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS1(l,j);
        if i<r then QS1(i,r);
end;
 
Procedure QS2(l,r:longint);
var     i, j, tg, xx    :longint;
begin
        i:=l;
        j:=r;
        xx:=k[(i+j) div 2];
        repeat
                while k[i]<xx do inc(i);
                while k[j]>xx do dec(j);
                if i<=j then
                        begin
                                hv(k[i],k[j]);
                                hv(csk[i],csk[j]);
                                hv(x[i],x[j]);
                                hv(y[i],y[j]);
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS2(l,j);
        if i<r then QS2(i,r);
end;
 
Procedure Update(x,v:longint);
begin
        while x<=maxn do
                begin
                        T[x]:=T[x]+v;
                        x:=x+x and (-x);
                end;
end;
 
Function Get(x:longint):longint;
begin
        Get:=0;
        while x>0 do
                begin
                        Get:=Get+t[x];
                        x:=x-x and (-x);
                end;
end;
 
Procedure xuly;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        csa[i]:=i;
                end;
        readln(q);
        for i:=1 to q do
                begin
                        readln(x[i],y[i],k[i]);
                        csk[i]:=i;
                end;
        QS1(1,n);
        QS2(1,q);
        for i:=1 to n do Update(i,1);
        j:=1;
        a[n+1]:=high(longint);
        for i:=1 to q do
                begin
                        while a[j]<=k[i] do
                                begin
                                        update(csa[j],-1);
                                        inc(j);
                                end;
                        if j<=n then
                                kq[csk[i]]:=Get(y[i])-Get(x[i]-1)
                        else kq[csk[i]]:=0;
                end;
        for i:=1 to q do writeln(kq[i]);
        close(input);close(output);
end;
 
begin
        xuly;
end.

LIQ và LIS sử dụng BIT – SPOJ

Đề bài:

Thuật toán:

  • Rời rạc hóa lại dãy
  • Gọi F[i] là độ dài dãy con tăng dài nhất kết thúc là số <= i
  • F[i] = max(F[1..a[i]-1] + 1)
  • Sử dụng cấu trúc dữ liệu BIT để tính mảng F trong O(logn)
  • ĐPT: O(nlogn)

Code:

using namespace std;
//#include<bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
 
int n, a[300010], T[300010], c[300010], f[300010], dem;
pair<int, int> b[300010];
 
int Get(int x)
{
    int ans = 0;
    if (x == 0) return 0;
    while (x > 0) {
        ans = max(ans, T[x]);
        x -= x & (-x);
    }
    return ans;
}
 
void Update(int x, int v)
{
    while (x <= n){
        T[x] = max(T[x], v);
        x += x & (-x);
    }
}
 
int main()
{
    //freopen("LIS.inp", "r", stdin);
    //freopen("LIS.out", "w", stdout);
    //cin>>n;
    scanf("%d", &n);
    FORE(i, 1, n) {
        //cin>>a[i];
        scanf("%d", &a[i]);
        b[i].first = a[i];
        b[i].second = i;
    }
 
    sort(b + 1, b + n + 1);
 
    int dem = 1; c[ b[1].second ] = dem;
    FORE(i, 2, n) {
        if (b[i].first > b[i - 1].first) dem++;
        c[ b[i].second ] = dem;
    }
    int ans = 0;
 
    FORE(i, 1, n) a[i] = c[i];
    //FORE(i, 1, n) cout<<a[i]<<" ";cout<<"=="<<endl;
    //cout<<"????"<<endl;
    FORE(i, 1, n) {
        f[i] = Get(a[i] - 1) + 1;
        Update(a[i], f[i]);
        ans = max(ans, f[i]);
    }
 
    //cout<<ans<<endl;
    printf("%d", ans);
    return 0;
}

BGMINE – SPOJ

Đề bài:

http://vn.spoj.com/problems/BGMINE/

Thuật toán:

Theo yêu cầu đề bài thì mình cần tìm một số hang liên tiếp mà có tổng số đá lớn hơn hoặc bằng độ dài các hang và có tổng số vàng lớn nhất đó: Sumr[j] – Sumr[i-1] >= x[j] – x[i] với (j >= i).

Ta biến đổi điều kiện trên thành: Sumr[j] – x[j] >= Sumr[i-1] – x[i] với (j >= i).

Ta sử dụng ctdl BIT để tính nhanh hơn. Ta cần rời rạc hóa giá trị Sumr[i] – x[i] và Sumr[i-1] – x[i] để lưa được trên cây BIT.

ĐPT: O(nlogn)

Code:

Pascal

uses math;
Const
  Fi='';
  Fo='';
  maxn=trunc(1e5)+3;
  oo=trunc(1e9);
var
  g,r,x : array[1..maxn] of longint;
  a  : array[1..2*maxn] of int64;
  cs,b,t : array[0..2*maxn] of longint;
  i,j,n : longint;
  best : int64;
  sr,sg : array[0..maxn] of int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i:=1 to n do read(x[i],g[i],r[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x; x:= y;y :=tg;
  end;
procedure qs(l,r : longint);
  var i,j :longint;
      x : int64;
  begin
    i := l;j :=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]<x do inc(i);
      while a[cs[j]]>x do dec(j);
      if i<=j then
        begin
          swap(cs[i],cs[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
  end;
procedure init;
  begin
    for i:=1 to n do sr[i] := sr[i-1] + r[i];
    for i:=1 to n do sg[i] := sg[i-1] + g[i];
  end;
procedure sub1;
  begin
    for i := 1  to n do
      for j:= i to n do
        begin
          if sr[j] - sr[i-1] >= x[j] - x[i] then
            begin
              best := max(best,sg[j]-sg[i-1]);
            end;
        end;
  end;
procedure roirac;
  var i,hold : longint;
  begin
    for i:=1 to n do a[i] := sr[i]-x[i];
    for i:=1 to n do a[n+i] := sr[i-1]-x[i];
    for i:=1 to 2*n do cs[i] := i;
    qs(1,2*n);
    b[cs[1]]  := 1; hold := 1;
    for i:=2 to 2*n do
      begin
        if a[cs[i]] = a[cs[i-1]] then
          begin
            b[cs[i]] := hold;
          end;
        if a[cs[i]] <> a[cs[i-1]] then
          begin
            inc(hold);
            b[cs[i]] := hold;
          end;
      end;
  end;
procedure update(i,x : longint);
  begin
    while i<=2*n do
      begin
        t[i] := min(t[i],x);
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  var res : longint;
  begin
    res := oo;
    while i>0 do
      begin
        res := min(res,t[i]);
        i := i - i and (-i);
      end;
    exit(res);
  end;
procedure sub2;
  var i,tg : longint;
  begin
    roirac;
    for i := 0 to 2*n+3 do t[i] := oo;
    for i:=1 to n do
      begin
        update(b[n+i],i);
        tg := get(b[i]);
        if tg<>oo then
          begin
            best := max(best, sg[i]-sg[tg-1]);
          end;
      end;
  end;
procedure process;
  begin
    sub2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(best);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

C++

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e5;
const int INF = 1e9 + 7;
 
int n;
int x[MAXN], a[MAXN], r[MAXN];
long long sr[MAXN], sx[MAXN], sg[MAXN];
void sub1()
{
    FORE(i, 1, n) sr[i] = sr[i - 1] + r[i];
    FORE(i, 1, n) sx[i] = sx[i - 1] + x[i];
    FORE(i, 1, n) sg[i] = sg[i - 1] + a[i];
    long long ans = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (sr[i] - sr[j] >= x[i] - x[j + 1]){
        ans = max(ans, sg[i] - sg[j]);
        //if (ans == 99) cout<<i<<" "<<j<<endl;
    }
    cout<< ans <<endl;
}
 
long long b[MAXN], T[MAXN], c[MAXN], sa[MAXN];
int get(int x)
{
    long long ans = INF;
    for(; x; x -= x & -x){
        ans = min(ans, T[x]);
    }
    return ans;
}
void update(int x, long long v)
{
    for(; x < MAXN; x+= x & -x) T[x] = min(T[x], v);
}
 
void sub2()
{
    sr[0] = 0;
    sa[0] = 0;
    FORE(i, 1, n){
        sa[i] = sa[i - 1] + a[i];
        sr[i] = sr[i - 1] + r[i];
        b[i] = sr[i] - x[i];
        b[i + n] = sr[i - 1] - x[i];
        c[i] = b[i];
        c[i + n] = b[i + n];
    }
    b[n + n + 1] = -x[1];
    c[n + n + 1] = -x[1];
    sort(c + 1, c + n + n + 2);
    FORE(i, 1, n + n + 1) b[i] = lower_bound(c + 1, c + n + n + 2, b[i]) - c;
    FOR(x, 0, 1e5 * 5) T[x] = INF;
    update(b[n + n + 1], 1);
    long long ans = 0;
    FORE(i, 1, n){
        int j = get(b[i]);
        //if (i == 41) cout<<j<<"wtf"<<endl;
        ans = max(ans, 1LL * a[i]);
        if (j != INF)
            ans = max(ans, sa[i] - sa[j - 1]);
        update(b[i + n], i);
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("MINE.inp", "r", stdin);
    freopen("MINE.out", "w", stdout);
    #endif // ONLINE_JUDGE
    //MIKELHPDATKE;
    cin >> n;
    FORE(i, 1, n) cin >> x[i] >> a[i] >> r[i];
    if (n <= 5000) sub1();
    else
    sub2();
    return 0;
}