Pohon Segmen

1. Introduction

Sebuah pohon segmen (Segment Tree / ST) adalah pohon biner yang dibuat berdasarkan sebuah array (biasanya integer) supaya kita dapat menyelesaikan query Range Min/Max/Sum serta query Range Update pada array tersebut dalam O(log N) dibandingkan dengan cara naif dalam O(N). Dengan sebuah array A dari N element, kita dapat membuat pohon segmen RMinQ/RMaxQ/RSumQ dalam O(N).