Struct SegTreeNode

Source

#[repr(transparent)]
pub struct SegTreeNode(pub usize);

Expand description

A node in a power-of-two layout segment tree.

This struct wraps a usize index representing a node’s position in the tree. The tree uses 1-based indexing for efficient parent/child calculations.

§Examples

use array_range_query::SegTreeNode;

let root = SegTreeNode(1);
let left_child = root.left_child();
let right_child = root.right_child();

assert_eq!(left_child.0, 2);
assert_eq!(right_child.0, 3);

Tuple Fields§

§0: usize

Implementations§

Source §

impl SegTreeNode

Source

pub fn left_child(&self) -> SegTreeNode

Returns the left child of this node.

Source

pub fn right_child(&self) -> SegTreeNode

Returns the right child of this node.

Source

pub fn parent(&self) -> SegTreeNode

Returns the parent of this node.

§Panics

Panics if called on the root node.

Source

pub fn sibling(&self) -> SegTreeNode

Returns the sibling of this node (assumes node is not root).

Source

pub fn sibling_safe(&self) -> SegTreeNode

Returns the sibling of this node.

§Panics

Panics if called on the root node.

Source

pub fn is_root(&self) -> bool

Returns true if this is the root node.

Source

pub fn is_left_child(&self) -> bool

Returns true if this node is a left child of its parent.

Source

pub fn is_left_child_if_not_root(&self) -> bool

Returns true if this node is a left child (assumes node is not root).

Source

pub fn is_right_child(&self) -> bool

Returns true if this node is a right child of its parent.

Source

pub fn is_right_child_if_not_root(&self) -> bool

Returns true if this node is a right child (assumes node is not root).

Source

pub fn depth(&self) -> u32

Returns the depth of this node (root is at depth 0).

Source

pub fn is_leaf(&self, max_depth: u32) -> bool

Returns true if this node is a leaf (at maximum depth).

§Parameters

max_depth: The maximum depth of the tree

§Examples

use array_range_query::SegTreeNode;

let root = SegTreeNode(1);
let leaf = SegTreeNode(8);
assert!(!root.is_leaf(3));
assert!(leaf.is_leaf(3));

Source

pub fn size(&self, max_depth: u32) -> usize

Returns the size of the range this node represents.

§Parameters

max_depth: The maximum depth of the tree (depth of leaf nodes)

§Examples

use array_range_query::SegTreeNode;

let root = SegTreeNode(1);
let leaf = SegTreeNode(8);
assert_eq!(root.size(3), 8);  // Root covers entire array of size 8
assert_eq!(leaf.size(3), 1);  // Leaf covers single element

Source

pub fn left_bound(&self, max_depth: u32) -> usize

Returns the left boundary of the range this node represents.

§Parameters

max_depth: The maximum depth of the tree (depth of leaf nodes)

§Examples

use array_range_query::SegTreeNode;

let node = SegTreeNode(2);  // Left child of root
assert_eq!(node.left_bound(3), 0);  // Covers [0, 4)

Source

pub fn right_bound(&self, max_depth: u32) -> usize

Returns the right boundary of the range this node represents.

§Parameters

max_depth: The maximum depth of the tree (depth of leaf nodes)

§Examples

use array_range_query::SegTreeNode;

let node = SegTreeNode(2);  // Left child of root
assert_eq!(node.right_bound(3), 4);  // Covers [0, 4)

Source

pub fn mid(&self, max_depth: u32) -> usize

Returns the midpoint of the range this node represents.

Source

pub fn node_bounds(&self, max_depth: u32) -> (usize, usize)

Returns the range [left, right) that this node represents.

§Parameters

max_depth: The maximum depth of the tree (depth of leaf nodes)

§Examples

use array_range_query::SegTreeNode;

let root = SegTreeNode(1);
assert_eq!(root.node_bounds(3), (0, 8));  // Root covers [0, 8)

Source

pub fn get_lca_from_same_depth( left: SegTreeNode, right: SegTreeNode, ) -> SegTreeNode

Finds the Lowest Common Ancestor (LCA) of two nodes at the same depth.

Source

pub fn get_lca_from_different_depth( left: SegTreeNode, right: SegTreeNode, ) -> SegTreeNode

Finds the Lowest Common Ancestor (LCA) of two nodes at potentially different depths.

Source

pub fn get_left_binding_node(&self) -> SegTreeNode

Returns the binding node by traversing up while this node is a right child. Used in segment tree range operations.

§Examples

use array_range_query::SegTreeNode;

let node = SegTreeNode(4);  // Left child
let binding = node.get_left_binding_node();
assert_eq!(binding, SegTreeNode(1));

Source

pub fn get_right_binding_node(&self) -> SegTreeNode

Returns the binding node by traversing up while this node is a right child. Used in segment tree range operations.

§Examples

use array_range_query::SegTreeNode;

let node = SegTreeNode(5);  // Right child
let binding = node.get_right_binding_node();
assert_eq!(binding, SegTreeNode(2));