Фенвикийн мод

Практик дээр динамикаар өөрчлөгддөг өгөгдлүүдтэй ажиллах шаардлага их гардаг. Фенвикийн мод нь байнга өөрчлөгдөж байж болох массивын дурын хэрчим дээрх хэсэгчилсэн нийлбэрийг олох хүсэлтэд хангалттай хурдан хариу өгдөг өгөгдлийн бүтэц юм.
N тооны элементтэй А массив өгөгдсөн байг: A0, A1, ..., AN-1. Фенвикийн модон дээр дараах хоёр үйлдлийг гүйцэтгэдэг:
rsq(i,j) – А массивын i-р болон j-р элемент дээр төгсгөлтэй хэрчмийн бүх элементүүдийн нийлэрийг буцаах (rsq гэдэг нь range sum query гэсний товчлол юм);
update(k,d) – A массивын k-р элемент дээр d тоог нэмэх.
rsq(i,j)-г энгийнээр зохион байгуулахад O(j-i+1) буюу O(N) хугацаанд, update(k,d) үйлдэл O(1) хугацаанд ажиллана. rsq(i,j) – ийн хувьд давталтаар өгөгдсөн хэрчим дэх элементүүдийг нэмэхэд хангалттай ба update(k,d)-ийн хувьд k-р элемент буюу Ak-г өөрчилнө.
Харин rsq(i,j) хэлбэрийн хангалттай олон тооны хүсэлт ирж байгаа тохиолдолд энгийн хэрэгжүүлэлт нь тийм ч их хурдан ажиллахгүй ба учир нь хүсэлт бүрийг массивын уртаас шугаман хамааралтай хугацаанд гүйцэтгэх болно.
Фенвикийн модыг ашиглан энэ хугацааг нэлээн багасгаж болно. Учир нь дээрх хоёр үйлдлийг хоёуланг нь O(log N) хугацаанд хийх боломжтой юм.