Prestress in amorphous solids bears the memory of their formation and plays a profound role in their mechanical properties, from stiffening or softening elastic moduli to shifting frequencies of vibrational modes, as well as directing yielding and solidification in the nonlinear regime. Here we develop a set of mathematical tools to investigate elasticity of prestressed discrete networks, which disentangles the effects from disorder in configuration and disorder in prestress. Applying these methods to prestressed triangular lattices and a computational model of amorphous solids, we demonstrate the importance of prestress on elasticity and reveal a number of intriguing effects caused by prestress, including strong spatial heterogeneity in stress-response unique to prestressed solids, power-law distribution of minimal dipole stiffness and a new criterion to classify floppy modes.