Số bài đã giải: 102
Hạng điểm: #3
Tổng điểm:
894,34
Đóng góp:
-3
Đã 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.Lịch sử rating
, #