• COOJ
  • Trang chủ
  • Danh sách bài
  • Các bài nộp
  • Thành viên
  • Các kỳ thi
  • Tổ chức
  • Thông tin
    >
    • Máy chấm
    • Custom Checkers
    • Github
VI EN Đăng nhập  hoặc  Đăng ký

quanghuy2701

  • Thông tin
  • Thống kê
  • Blog

Số bài đã giải: 102
Hạng điểm: #3
Tổng điểm: 894,34
Đóng góp: -3

Xem các bài nộp

Đã tham gia 1 kỳ thi
Hạng rating: #7
Rating: 1165
Min. rating: 1165
Max rating: 1165

Từ Đội tuyển HSG Tin học FPTSchools

Thông tin

Let ~f~  be some group operation (a binary associative function over a set with an identity element and inverse elements) and ~A~ be an array of integers of length ~N~. Denote ~f~'s infix notation as ~*~; that is, ~f(x,y) = x*y~ for arbitrary integers ~x,y~. (Since this is associative, we will omit parentheses for order of application of ~f~ when using infix notation.)

The Fenwick tree is a data structure which:

  • calculates the value of function ~f~ in the given range ~[l, r]~ (i.e. ~A_l * A_{l+1} * \dots * A_r~) in ~O(\log N)~ time
  • updates the value of an element of ~A~ in ~O(\log N)~ time
  • requires ~O(N)~ memory (the same amount required for ~A~)
  • is easy to use and code, especially in the case of multidimensional arrays

Huy hiệu

Người dùng này không có huy hiệu nào.

«    »
CN
T2
T3
T4
T5
T6
T7
Ít
Nhiều

Lịch sử rating

, #

dựa trên nền tảng DMOJ | theo dõi VNOI trên Github và Facebook