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)