Spatial attention can be deployed with a narrower focus to process individual items or distributed relatively broadly to process larger parts of a scene. This study investigated how focused- versus distributed-attention modes contribute to the adaptation of context-based memories that guide visual search. In two experiments, participants were either required to fixate the screen center and use peripheral vision for search (“distributed attention”), or they could freely move their eyes, enabling serial scanning of the search array (“focused attention”). Both experiments consisted of an initial learning phase and a subsequent test phase. During learning, participants searched for targets presented either among repeated (invariant) or nonrepeated (randomly generated) spatial layouts of distractor items. Prior research showed that repeated encounters of invariant display arrangements lead to long-term context memory about these arrays, which can then come to guide search (contextual-cueing effect). The crucial manipulation in the test phase was a change of the target location within an otherwise constant distractor layout, which has previously been shown to abolish the cueing effect. The current results replicated these findings, although importantly only when attention was focused. By contrast, with distributed attention, the cueing effect recovered rapidly and attained a level comparable to the initial effect (before the target location change). This indicates that contextual cueing can adapt more easily when attention is distributed, likely because a broad attentional set facilitates the flexible updating of global (distractor-distractor), as compared to more local (distractor-target), context representations—allowing local changes to be incorporated more readily.