A tracker of slot usage for a region spanning a total of 2^14 (16384) slots, in a total of 3072 bytes using a combination of a Fenwick tree and a bitmap vector.

UsageTrackingBlock.cs

namespace TryOuts
{
    using System.Linq;
    using System.Diagnostics;
    using System.Collections.Generic;

    /// <summary>
    /// Tracks usage of a block of 2^14 (16384) slots using a bitmap that 
    /// contains the 16384 used/free bit flags for each slot (taking up a 
    /// total space of 2048 bytes, accessed as an array of 512 ints), in 
    /// combination with a Fenwick tree that contains the counts of slots 
    /// in use in the block from the level of 2^14 down to the level of 
    /// 2^5 (32 slot in a block). Thus the Fenwick tree requires 1024 bytes 
    /// of storage accessed as an array of 512 ushorts. 
    /// It allows O(log N) updates, point and range queries for the amount 
    /// of free and used slots in the block. 
    /// Unfortunately searches for contiguous ranges of a given number of
    /// free or used slots is quite a bit more involved (the current 
    /// implementations of "GetIndexOfFirstUsedBlockFromLevel" and 
    /// "GetIndexOfLastUsedBlockUpToLevel" are not fully correct and don't
    /// help sufficiently in efficient contiguous range searches).
    /// </summary>
    public class UsageTrackingBlock
    {
        const int TotalSlotsInBlockPower = 14;
        const int BlockGranularityPower = 5;
        const int BlockGranularity = 1 << BlockGranularityPower; // 32
        const int FenwickTreeCoveredPowers = TotalSlotsInBlockPower - BlockGranularityPower; // 9
        const int FenwickTreeSize = 1 << FenwickTreeCoveredPowers; // 512. 
        const int NumberOfBitmapEntries = BlockCapacityInSlots / sizeof(int); // 512
        const int BlockBitmapIndexModulus = BlockGranularity - 1; // 31: 00011111

        private readonly int[] _slotUsageBitmap = new int[NumberOfBitmapEntries]; // 512 * 4 = 2048 bytes
        private readonly ushort[] _fenwickSlotUsageTree = new ushort[FenwickTreeSize]; // 512 * 2 = 1024 bytes
        private readonly long _firstSlotInBlock;

        public UsageTrackingBlock(long firstSlotInBlock)
        {
            // Usage blocks must be aligned per 2^14 slots.
            Debug.Assert(firstSlotInBlock % BlockCapacityInSlots == 0);
            _firstSlotInBlock = firstSlotInBlock;
        }

        public const int BlockCapacityInSlots = 1 << TotalSlotsInBlockPower; // 16384
        public long FirstSlotInBlock
        {
            get { return _firstSlotInBlock; }
        }
        public long LastSlotInBlock
        {
            get { return _firstSlotInBlock + BlockCapacityInSlots - 1; }
        }
        public long FirstSlotInNextBlock
        {
            get { return _firstSlotInBlock + BlockCapacityInSlots; }
        }

        public int TotalSlotsInUse
        {
            get { return _fenwickSlotUsageTree[FenwickTreeSize - 1]; }
        }

        public int TotalSlotsFree
        {
            get { return BlockCapacityInSlots - TotalSlotsInUse; }
        }

        public bool IsUsed(long slotNumber)
        {
            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            var bitmapIndex = slotIndex >> BlockGranularityPower;
            var bitIndex = slotIndex & (BlockBitmapIndexModulus);
            return ((_slotUsageBitmap[bitmapIndex] & (1 << bitIndex)) != 0);
        }

        public bool IsFree(long slotNumber)
        {
            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            var bitmapIndex = slotIndex >> BlockGranularityPower;
            var bitIndex = slotIndex & (BlockBitmapIndexModulus);
            return ((_slotUsageBitmap[bitmapIndex] & (1 << bitIndex)) == 0);
        }

        public void MarkFree(long slotNumber)
        {
            AssertSlotIsInBlock(slotNumber);
            Debug.Assert(IsUsed(slotNumber));

            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            var blockIndex = slotIndex >> BlockGranularityPower;

            // update bitmap.
            _slotUsageBitmap[blockIndex] &= ~(1 << (slotIndex & BlockBitmapIndexModulus));

            // update slot usage counts in fenwick tree.
            for (; blockIndex < _fenwickSlotUsageTree.Length; blockIndex += ((blockIndex + 1) & -(blockIndex + 1)))
                _fenwickSlotUsageTree[blockIndex]--;
        }

        public void MarkFree(IEnumerable<long> slotNumbers)
        {
            // Group needed info per 32 slot block, so we only need to do
            // block updates.
            var blockUpdateInfo = slotNumbers
                .Select(p => unchecked((int)(p - _firstSlotInBlock)))
                .GroupBy(pi => pi >> BlockGranularityPower)
                .Select(bl => new 
                { 
                    BlockIndex = bl.Key, 
                    Amount = (ushort)bl.Count(), 
                    Mask = bl.Aggregate(0, (mask, slotIndex) => mask |= (1 << (slotIndex & BlockBitmapIndexModulus))) 
                })
                .ToArray();

            for (int i = 0; i < blockUpdateInfo.Length; i++)
            {
                var blockIndex = blockUpdateInfo[i].BlockIndex;

                // update bitmap.
                _slotUsageBitmap[blockIndex] &= ~blockUpdateInfo[i].Mask;

                // update slot usage counts in fenwick tree.
                for (; blockIndex < _fenwickSlotUsageTree.Length; blockIndex += ((blockIndex + 1) & -(blockIndex + 1)))
                    _fenwickSlotUsageTree[blockIndex] -= blockUpdateInfo[i].Amount;
            }
        }

        public void MarkUsed(long slotNumber)
        {
            AssertSlotIsInBlock(slotNumber);
            Debug.Assert(IsFree(slotNumber));

            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            var blockIndex = slotIndex >> BlockGranularityPower;

            // update bitmap.
            _slotUsageBitmap[blockIndex] |= (1 << (slotIndex & BlockBitmapIndexModulus));

            // update slot usage counts in fenwick tree.
            for (; blockIndex < _fenwickSlotUsageTree.Length; blockIndex += ((blockIndex + 1) & -(blockIndex + 1)))
                _fenwickSlotUsageTree[blockIndex]++;
        }

        public void MarkUsed(IEnumerable<long> slotNumbers)
        {
            // Group needed info per 32 slot block, so we only need to do
            // block updates.
            var blockUpdateInfo = slotNumbers
                .Select(p => unchecked((int)(p - _firstSlotInBlock)))
                .GroupBy(pi => pi >> BlockGranularityPower)
                .Select(bl => new
                {
                    BlockIndex = bl.Key,
                    Amount = (ushort)bl.Count(),
                    Mask = bl.Aggregate(0, (mask, slotIndex) => mask |= (1 << (slotIndex & BlockBitmapIndexModulus)))
                })
                .ToArray();

            for (int i = 0; i < blockUpdateInfo.Length; i++)
            {
                var blockIndex = blockUpdateInfo[i].BlockIndex;

                // update bitmap.
                _slotUsageBitmap[blockIndex] |= blockUpdateInfo[i].Mask;

                // update slot usage counts in fenwick tree.
                for (; blockIndex < _fenwickSlotUsageTree.Length; blockIndex += ((blockIndex + 1) & -(blockIndex + 1)))
                    _fenwickSlotUsageTree[blockIndex] += blockUpdateInfo[i].Amount;
            }
        }

        public int NumberOfSlotsUsedUpTo(long slotNumber)
        {
            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            return SumUsed(slotIndex);
        }

        public int NumberOfSlotsFreeUpTo(long slotNumber)
        {
            var slotIndex = unchecked((int)(slotNumber - _firstSlotInBlock));
            return (slotIndex + 1) - SumUsed(slotIndex);
        }

        public int NumberOfSlotsUsedInRange(long first, long last)
        {
            var firstIndex = unchecked((int)(first - _firstSlotInBlock));
            var lastIndex = unchecked((int)(last - _firstSlotInBlock));
            return SumUsed(lastIndex) - SumUsed(firstIndex - 1);
        }

        public int NumberOfSlotsFreeInRange(long first, long last)
        {
            var firstIndex = unchecked((int)(first - _firstSlotInBlock));
            var lastIndex = unchecked((int)(last - _firstSlotInBlock));
            return (lastIndex - firstIndex + 1) - (SumUsed(lastIndex) - SumUsed(firstIndex - 1));
        }

        public int NumberOfLeadingFreeSlots
        {
            get
            {
                return (TotalSlotsInUse == 0) ? BlockCapacityInSlots : GetNumberOfLeadingFreeSlotsAtLevel(-1, FenwickTreeSize);
            }
        }

        public int NumberOfTrailingFreeSlots
        {
            get 
            {
                return GetNumberOfTrailingFreeSlotsUpToLevel(FenwickTreeSize);
            }
        }

        public long GetFirstSlotInUse()
        {
            if (TotalSlotsInUse == 0)
                return -1; // no slots.
            return _firstSlotInBlock + NumberOfLeadingFreeSlots;
        }

        public long GetLastSlotInUse()
        {
            if (TotalSlotsInUse == 0)
                return -1;
            return _firstSlotInBlock + BlockCapacityInSlots - NumberOfTrailingFreeSlots;
        }

        private int SumUsed(int upToAndIncludingSlotIndex)
        {
            var remainder = upToAndIncludingSlotIndex & BlockBitmapIndexModulus;
            var blockIndex = upToAndIncludingSlotIndex >> BlockGranularityPower;

            // Initialize result to the negative value of the # of bits that
            // are set after the given slot index in the 32-slot block that
            // contains this slot. These should be subtracted from the Fenwick 
            // tree sum.
            var remainderBlockBitmap = unchecked((uint)(_slotUsageBitmap[blockIndex] >> (remainder + 1)));
            int result = remainderBlockBitmap != 0 ? -Bits.PopCount(remainderBlockBitmap) : 0;

            // Fenwick tree sum.
            for (; blockIndex >= 0; blockIndex -= ((blockIndex + 1) & -(blockIndex + 1)))
                result += _fenwickSlotUsageTree[blockIndex];

            return result;
        }

        public int GetIndexOfFirstUsedBlockFromLevel(int startPos, int startLevel)
        {
            Debug.Assert(Bits.IsPowerOf2(startLevel));
            var pos = startPos;
            for (var level = startLevel; level > 0; level >>= 1)
            {
                var nextPos = pos + level;
                if (nextPos >= FenwickTreeSize)
                    break;
                if (_fenwickSlotUsageTree[nextPos] == 0)
                    pos = nextPos;
            }
            return pos + 1;
        }

        public int GetIndexOfLastUsedBlockUpToLevel(int upToLevel)
        {
            Debug.Assert(Bits.IsPowerOf2(upToLevel));
            var pos = -1;
            var totals = (int)_fenwickSlotUsageTree[pos + upToLevel];
            if (totals == 0)
                return upToLevel;
            for (var level = upToLevel; level > 0; level >>= 1)
            {
                var nextPos = pos + level;
                if (nextPos >= FenwickTreeSize)
                    break;
                if (_fenwickSlotUsageTree[nextPos] < totals)
                {
                    totals = totals - _fenwickSlotUsageTree[nextPos];
                    pos = nextPos;
                }
            }
            return pos + 1;
        }

        public int GetNumberOfLeadingFreeSlotsAtLevel(int startPos, int startLevel)
        {
            var firstBlockInUse = GetIndexOfFirstUsedBlockFromLevel(startPos, startLevel);
            var lsb = Bits.BitScanForward32(_slotUsageBitmap[firstBlockInUse]);
            return firstBlockInUse * BlockGranularity + (int)lsb;
        }

        public int GetNumberOfTrailingFreeSlotsUpToLevel(int level)
        {
            var lastBlockInUse = GetIndexOfLastUsedBlockUpToLevel(level);
            if (lastBlockInUse < level)
            {
                var lsb = Bits.BitScanForward32(_slotUsageBitmap[lastBlockInUse]);
                return ((level - lastBlockInUse) * BlockGranularity) - (1 + (int)lsb);
            }
            return level * BlockGranularity;
        }

        [Conditional("DEBUG")]
        private void AssertSlotIsInBlock(long slotNumber)
        {
            Debug.Assert(slotNumber >= _firstSlotInBlock);
            Debug.Assert(slotNumber < _firstSlotInBlock + BlockCapacityInSlots);
        }
    }
}