cây nhị phân mà các cửa hàng tiền từng phần: Tên và triển khai hiện

Question

Hãy xem xét một chuỗi các n số thực dương, (một _i), và trình tự tổng hợp một phần của nó, (s _i). Cho một số x ε (0, s _n], chúng tôi phải tìm i mà s_{i -1} < x ≤ s _i. Cũng chúng tôi muốn có thể thay đổi một trong số a _i mà không phải cập nhật tất cả các khoản tiền một phần. Cả hai có thể được thực hiện trong O (log n) thời gian bằng cách sử dụng cây nhị phân với các giá trị nút lá _i và giá trị của các nút không phải lá là tổng của các giá trị của các con tương ứng. Nếu n được biết và cố định, cây không phải tự cân bằng và có thể được lưu trữ hiệu quả trong một mảng tuyến tính. Hơn nữa, nếu n là công suất của hai, chỉ cần có 2 thành phần mảng n - 1. Xem Blue và cộng sự, Phys. Rev. E (1995), tr. R867 – R868 cho một ứng dụng. Do tính tổng quát của vấn đề và sự đơn giản của giải pháp, tôi tự hỏi liệu cấu trúc dữ liệu này có một tên cụ thể và liệu có các triển khai hiện có hay không (tốt nhất là trong C++). Tôi đã tự mình thực hiện, nhưng việc viết cấu trúc dữ liệu từ đầu luôn có vẻ như tạo lại bánh xe cho tôi — tôi sẽ ngạc nhiên nếu không ai làm điều đó trước đây.

Answer 1

Fenwick tree (còn gọi là cây được lập chỉ mục nhị phân) là cấu trúc dữ liệu duy trì một chuỗi phần tử và có thể tính tổng tích lũy của bất kỳ phạm vi phần tử liên tiếp nào trong thời gian O (logn). Thay đổi giá trị của bất kỳ phần tử đơn lẻ nào cũng cần thời gian O (logn).

Answer 2

Điều này được gọi là finger tree trong lập trình hàm nhưng dường như có các triển khai bằng ngôn ngữ mệnh lệnh. Trong các bài báo có một liên kết đến một số blog post giải thích việc triển khai cấu trúc dữ liệu này trong C# có thể hữu ích cho bạn.