Randomly selecting element from data structure, probability based on weight
I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children.
To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know where in the heap is stored an element with given id.

To know how to select an element, when exploring the tree t of weight t.weight, you can generate a number r between $0$ and t.weight, and go left if r &lt; t.left.weight and right otherwise.
To insert, just put it at the last available leaf position and modify the weights of all its ancestors.
To delete, switch the position with the last leaf, and modify the ancestors of both the deleted node and the switched leaf.
To modify weight, use the corresponding structure to know the position of the element of given id, and modify the weights of its ancestors.

All operations can be done in $O(\log n)$.