Possible ways to fix segment tree implementation?

So, I tried to implement a segment tree in roblox and it seemed to be working fine for a few arrays until I tried to get it to build a tree for an array of 10 items, all the values being 0.1. It did some weird stuff, and the left child of the root node became 0.6, and right child 0.4. I tried to go through the algorithm visually and managed to construct an explanation of what was happening:

Any ideas on how I could fix this?
Here is the code:

local Rand = Random.new()
local Tree

local function Build(Arr,N)

	Tree = {}
	for i = 1,2 * N - 1 do
		table.insert(Tree,{Value = 0,Min = 9999,Max = -9999})
	end

	if N % 2 == 0 then
		for i = 1,N do
			Tree[N + i - 1].Value = Arr[i]
		end
	else
		Tree[N].Value = Arr[N]

		for i = 2,N do
			Tree[N + i - 1].Value = Arr[i - 1]
		end
	end

	for i = N - 1,1,-1 do
		local LChild = Tree[bit32.lshift(i,1)]
		local RChild = Tree[bit32.lshift(i,1) + 1]
		local IsFirstLayerAboveArray = Tree[bit32.lshift(i,1)].Max == -9999

		if IsFirstLayerAboveArray then
			if RChild.Value > LChild.Value then
				Tree[i].Max = RChild.Value
				Tree[i].Min = LChild.Value
			else
				Tree[i].Max = LChild.Value
				Tree[i].Min = RChild.Value
			end
		else
			if RChild.Max > LChild.Max then
				Tree[i].Max = RChild.Max
			else
				Tree[i].Max = LChild.Max
			end

			if RChild.Min < LChild.Min then
				Tree[i].Min = RChild.Min
			else
				Tree[i].Min = LChild.Min
			end
		end

		Tree[i].Value = RChild.Value + LChild.Value
	end
end

local function RetrieveValue(Position,N)
	if N % 2 == 0 then
		return Tree[Position + N - 1].Value
	else
		if Position == N then
			return Tree[N].Value
		else
			return Tree[N + Position].Value
		end
	end
end

local function UpdateTreeNode(Position,Value,N)
	local Old = RetrieveValue(Position,N)
	local Change = Value - Old
	local Index

	if N % 2 == 0 then
		Tree[Position + N - 1].Value = Value

		Index = Position + N - 1
	else
		if Position == N then
			Tree[N].Value = Value

			Index = N
		else
			Index = Position + N
			Tree[Index].Value = Value
		end
	end

	while Index > 1 do
		local ParentIndex = bit32.rshift(Index,1)
		--Compare Index and Index - 1
		if Tree[Index].Max == -9999 then --Layer above array layer
			if Tree[Index].Value > Tree[Index - 1].Value then -- Compare right child and left child
				Tree[ParentIndex].Max = Tree[Index].Value
				Tree[ParentIndex].Min = Tree[Index - 1].Value
			else
				Tree[ParentIndex].Max = Tree[Index - 1].Value
				Tree[ParentIndex].Min = Tree[Index].Value
			end
		else
			if Tree[Index].Max > Tree[Index - 1].Value then
				Tree[ParentIndex].Max = Tree[Index].Max
				Tree[ParentIndex].Min = Tree[Index - 1].Min
			else
				Tree[ParentIndex].Max = Tree[Index - 1].Max
				Tree[ParentIndex].Min = Tree[Index].Min
			end
		end

		Tree[ParentIndex].Value = Tree[ParentIndex].Value + Change
		Index = bit32.rshift(Index,1)
	end
end

local function WeightedSampling(min,max,N)
	local Uniform = Rand:NextNumber(min,max)

	local Index = 1

	while Index ~= math.clamp(Index,N,2 * N - 1) do
		local LCIndex = bit32.lshift(Index,1)
		local RCIndex = LCIndex + 1
		local LeftChild = Tree[LCIndex].Value
		local RightChild = Tree[RCIndex].Value
		
		if Uniform < LeftChild then
			Index = LCIndex
		else
			Uniform = Uniform - LeftChild
			Index = RCIndex
		end
	end

	return Index - N + 1,Index
end

local Array = table.create(10,0.1)
local N = #Array

Build(Array,N)

print(Tree)

Try to separate a new method that swaps child and parent nodes. Maybe that will clear up some confusions?

What do you mean by swapping child and parent nodes?

It looks like there may be a few issues with the code you posted. In the Build function, the code that is used to set the values of the leaf nodes (i.e., the nodes that correspond to the original array) is dependent on whether N is odd or even. This seems unnecessary, as the values of the leaf nodes can simply be set to the corresponding values from the input array in a loop.

Additionally, the code that is used to propagate values up the tree (i.e., from leaf nodes to the root) appears to be incorrect. In particular, the if IsFirstLayerAboveArray then block of code does not update the Value field of the current node, which is why the root node ends up with a Value of 0.6 in your example.

I would recommend simplifying the code and ensuring that all nodes in the tree are properly updated when building the tree and when updating individual nodes. You may also want to consider using a different approach to build and update the tree, such as using a recursive function or using a queue to traverse the tree in breadth-first order.

1 Like

This is a sample on how you could build and update a segment tree using a recursive function:

local function buildSegmentTree(arr, start, endF)
	-- base case: leaf node, return node with value from array
if start == endF then
	return { value = arr[start], min = arr[start], max = arr[start] }
end

-- compute the middle index of the current range
local mid = math.floor((start + endF) / 2)

	-- recursively build left and right subtrees
local left = buildSegmentTree(arr, start, mid)
local right = buildSegmentTree(arr, mid + 1, endF)

	-- combine values from left and right subtrees to create the current node
local node = {
	value = left.value + right.value,
	min = math.min(left.min, right.min),
	max = math.max(left.max, right.max),
}

return node
end

local function updateSegmentTree(node, i, val, start, endF)
	-- base case: leaf node
if start == endF then
	node.value = val
	node.min = val
	node.max = val
	return
end

-- compute the middle index of the current range
local mid = math.floor((start + endF) / 2)

	-- update the appropriate subtree
if i <= mid then
	updateSegmentTree(node.left, i, val, start, mid)
else
	updateSegmentTree(node.right, i, val, mid + 1, endF)
end

-- combine values from left and right subtrees to update current node
node.value = node.left.value + node.right.value
node.min = math.min(node.left.min, node.right.min)
node.max = math.max(node.left.max, node.right.max)
end

-- example usage

local arr = {0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1}
local root = buildSegmentTree(arr, 1, #arr)

-- update the value at index 5 to 0.2
updateSegmentTree(root, 5, 0.2, 1, #arr)

I accidentally used end instead of a better parameter name.

Actually, the root node ends up with a value of 1 in my example and the value of the current node is being updated.

Tree[i].Value = RChild.Value + LChild.Value

But I do appreciate the answer. This method seems a lot less convoluted than what I was doing so I will try implementing your method.

The recursion got me totally lost but I think I understand it. A few questions though. In the local function updateSegmentTree do you update it from the top-down or bottom-up? What’s the node parameter used for?

Let me explain everything:

The code defines two functions: buildSegmentTree and updateSegmentTree .

The buildSegmentTree function takes as input an array of values ( arr ), a start index ( start ), and an end index ( endF ), and returns a tree structure representing the input array. The tree is built recursively by dividing the current range of indices in the array into two halves, creating a left and right subtree for each half, and then combining the values from the left and right subtrees to create the current node in the tree. The function returns the root node of the tree.

The updateSegmentTree function takes as input a node in the tree ( node ), an index in the array ( i ), a new value for that index ( val ), a start index ( start ), and an end index ( endF ). The function updates the tree to reflect the new value at the given index in the array by recursively updating the appropriate subtree and then combining the values from the left and right subtrees to update the current node.

The code then provides an example usage of these functions by creating an array of ten values and building a segment tree from it, and then updating the value at index 5 in the array to 0.2 and updating the tree accordingly.

  1. In the updateSegmentTree function, the tree is updated from the bottom-up. This means that when the function is called, it first updates the value at the leaf node in the tree corresponding to the given index in the array, and then it propagates the changes upwards through the tree by updating the parent nodes of the leaf node. This allows the entire tree to be updated to reflect the new value in the array in an efficient manner.
  2. In the updateSegmentTree function, the node parameter represents a node in the segment tree. The function takes this node as input and updates its values to reflect the new value in the array. Because the segment tree is built recursively, node can refer to any node in the tree, not just the root node. The function will update the values of the node and its children as necessary to reflect the new value in the array.

I hope this satisfies your needs.

I’ve noticed that you did:

if i <= mid then
	updateSegmentTree(node.left, i, val, start, mid)
else
	updateSegmentTree(node.right, i, val, mid + 1, endF)
end

Wouldn’t this error because there is no left or right property of node?

Yes, you are correct. In the updateSegmentTree function, the code attempts to access the left and right properties of the node parameter, but it is possible that these properties do not exist. This could cause the code to throw an error.

To fix this issue, you could check whether the node parameter has the left and right properties before trying to access them. This can be done with an if statement, for example:

if node.left and node.right then
	if i <= mid then
		updateSegmentTree(node.left, i, val, start, mid)
	else
		updateSegmentTree(node.right, i, val, mid + 1, endF)
	end
else
	-- Handle the case where the left or right property does not exist
end

This will check whether the node parameter has both the left and right properties, and only try to access them if they both exist. This should prevent the error from occurring.

Addititionally to that I added:

local node = {
		value = left.value + right.value,
		min = math.min(left.min, right.min),
		max = math.max(left.max, right.max),
		left = left,
		right = right
	}

To the buildSegmentTree function. Now I think I understand what it’s doing. It’s creating a root node which has 2 sub-arrays as its “children” then those children have sub-arrays and so on until it reaches the leaf node. Is this correct?

Indeed. The buildSegmentTree function creates a segment tree, which is a tree-like data structure that can be used to efficiently perform range queries on an array. In this particular implementation, the segment tree stores information about the sum, minimum, and maximum value in each sub-range of the input array.

Here’s how it works: the function takes in the input array arr , as well as the start and end indices of the current range that we are building the segment tree for. If the start index and the end index are the same (i.e., if we have reached a leaf node), then the function simply creates a node with the value of the corresponding element in the input array.

If we haven’t reached a leaf node yet, then the function recursively builds the left and right subtrees by calling buildSegmentTree with the appropriate range of indices. Once the left and right subtrees have been built, the function combines the values from the left and right subtrees to compute the value, minimum, and maximum for the current node. Finally, the function returns the current node.

The updateSegmentTree function works in a similar way, but instead of building the tree from scratch, it updates an existing tree with a new value for a particular element in the input array. It takes in the root node of the tree, the index of the element to update, the new value, and the start and end indices of the current range. If the start index and the end index are the same (i.e., if we have reached a leaf node), then the function simply updates the value, minimum, and maximum for the current node.

If we haven’t reached a leaf node yet, then the function updates the appropriate subtree by calling updateSegmentTree with the appropriate range of indices. Once the left and right subtrees have been updated, the function combines the values from the left and right subtrees to update the value, minimum, and maximum for the current node. It then returns the updated tree.

The segment tree data structure allows us to efficiently perform range queries on the input array, such as computing the sum or the minimum or maximum value in a given range. This can be done by traversing the tree and only considering the nodes that intersect with the range of interest. Since the height of the tree is logarithmic in the length of the input array, this allows us to perform range queries in logarithmic time.

If you want to know something else, please reply with a detailed explanation of what you are trying to accomplish.

1 Like

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.