Why is List.Add O(lg n) for immutable? You can abuse the fact that any subset of an immutable list is immutable to make it O(1) surely:

class ImmutableList<T> 
{
  int cachedPrefixLen = -1;
  Immutable<T> prefix;
  T[] item;
  ImmutableList<T>(Immutable<T> prefix, params T[] nextItems)
  {
    prefix = prefix:
    item = nextItems;

  }
  public ImmutableList<T> Add(T item)
  {
    // O(1)
    return new ImmutableList(this, item);
  }
  public ImmutableList<T> AddRange(T[] items)
  {
    // O(1)
    return new ImmutableList(this, items);
  }
  private int PrefixLen { get { if(cachedPrefixLen == -1) cachedPrefixLen = prefix == null? 0 : prefix.Count; return cachedPrefixLen; }}
  public int Count { get { return PrefixLen + item.Length; } }
  public void ToArray(T[] dst, int offset, int count)
  {
    int a = Math.Min(dst.Length, count);
    int b = count - a;
    prefix.ToArray(dst, offset, a);
    Array.Copy(dst, offset + a, b);
  }
  public bool Contains(T t)
  {
    return prefix.Contains(item) || item.Contains(t);
  }

  public T this[int index] 
  {
    get { if(index < PrefixLen) return prefix[index]; else return items[PrefixLen - index];
  }

// etc
}