Metadata-Version: 2.4
Name: dynamic-segment-tree
Version: 0.1.0
Summary: Dynamic segment tree with Python bindings
Author: Abdullah Enes Oncu
Author-email: abdullahenesoncu@gmail.com
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C++
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.7
Description-Content-Type: text/markdown
Requires-Dist: pybind11>=2.6.0
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

# Dynamic Segment Tree

A high-performance dynamic segment tree implemented in C++ with Python bindings using pybind11.  
Supports efficient range queries and updates on large arrays without reserving memory upfront.

## About Dynamic Segment Tree

This package implements a **dynamic segment tree** data structure for efficient use in Python programs.

### What is a dynamic segment tree?

- A **segment tree** is a powerful data structure used to perform **range queries and updates** efficiently on an array.
- The **dynamic** variant does **not pre-allocate memory for the entire array size**, but instead **creates nodes only when needed**, saving memory.
- This makes it practical for very large arrays (e.g., length 10 million or more) where many elements are initially zero or default.

### What problem does this solve?

- Suppose you have **M categories** and an array of length N.
- At each position, exactly one category is assigned.
- You want to:
  - **Update** the category at any index dynamically.
  - **Query** how many elements of a given category exist in any range `[L, R]`.
- This package supports exactly that efficiently, using minimal memory.

## Main Functions

### `DynamicSegTree(N)`

- Creates a dynamic segment tree for an array of size `N`.
- Initially, all positions are empty (or a default invalid category).

### `build(arr)`

- Builds the tree from a given list/array `arr` of categories.
- This initializes the data structure with known values.

### `set(pos, category)`

- Updates the element at position `pos` to belong to `category`.
- If the position already had a category, it updates it accordingly.

### `get(pos)`

- Returns the current category at position `pos`.
- Returns `-1` if the position is unset or empty.

### `query(l, r, category)`

- Returns the **count** of elements belonging to `category` in the range `[l, r]`.
- This is the main query function and works efficiently even for large `N`.

## Why Use This Package?

- Designed for very large arrays where a classical segment tree would be memory-heavy.
- Provides a Python interface for easy integration into your projects.
- Efficiently supports queries and updates with **logarithmic time complexity**.
- Ideal for problems involving category counts over large ranges with sparse updates.

## Installation

```bash
pip install dynamic-segment-tree
