线段树：解决区间查询和区间修改的利器

线段树是一种非常有用的数据结构，它可以在 $O(\log n)$ 的时间内支持区间修改和查询。在本文中，我们将介绍线段树的基本概念和实现方法，并通过一个例子来说明其使用方法。

基本概念

线段树是一种二叉树结构，用于处理区间查询和修改操作。它将一个区间分成多个小的子区间，然后用树状结构来表示这些子区间。每个节点代表一个区间，它的左右儿子代表该区间的两个子区间。叶子节点表示区间中的单个元素。

线段树的建立是通过递归的方式进行的。首先将整个区间分成两半，然后分别递归地建立左右子树。每个节点保存了其对应区间内的信息，例如区间和、最大值等。

实现方法

下面是一个简单的线段树实现。我们使用 JavaScript 来演示。假设我们要实现一个支持区间求和操作的线段树，下面是代码实现：

class SegmentTree {
  constructor(nums) {
    this.nums = nums;
    this.tree = new Array(nums.length * 4).fill(0);
    this.build(0, 0, nums.length - 1);
  }

  build(node, start, end) {
    if (start === end) {
      this.tree[node] = this.nums[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(node * 2 + 1, start, mid);
      this.build(node * 2 + 2, mid + 1, end);
      this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
    }
  }

  update(node, start, end, i, val) {
    if (start === end) {
      this.nums[i] = val;
      this.tree[node] = val;
    } else {
      const mid = Math.floor((start + end) / 2);
      if (i >= start && i <= mid) {
        this.update(node * 2 + 1, start, mid, i, val);
      } else {
        this.update(node * 2 + 2, mid + 1, end, i, val);
      }
      this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
    }
  }

  query(node, start, end, i, j) {
    if (i > end || j < start) {
      return 0;
    }
    if (i <= start && j >= end) {
      return this.tree[node];
    }
    const mid = Math.floor((start + end) / 2);
    return this.query(node * 2 + 1, start, mid, i, j) + this.query(node * 2 + 2, mid + 1, end, i, j);
  }
}

const nums = [1, 3, 5, 7, 9, 11];
const st = new SegmentTree(nums);

console.log(st)

应用实例

线段树的应用非常广泛，下面我们通过一个例子来说明其使用方法。假设我们有一个长度为 $n$ 的数组 $a$，需要支持以下两种操作：

1. 修改数组中的某个元素 $a_i$ 的值为 $v$。
2. 查询区间 $[l,r]$ 的元素和。

使用线段树可以很方便地实现这两个操作。我们首先需要建立一棵线段树，将数组中的元素保存在叶子节点上。每个节点保存了其对应区间内的元素和，以支持区间查询。

当需要修改某个元素时，我们可以使用线段树的 update 操作来实现。具体来说，我们从根节点开始递归，找到对应叶子节点，并将其值修改为新的值 $v$。同时，我们还需要更新该节点对应的父节点、祖先节点的值，以保证线段树的正确性。

当需要查询某个区间的元素和时，我们可以使用线段树的 query 操作来实现。具体来说，我们从根节点开始递归，找到包含区间 $[l,r]$ 的节点。如果该节点的区间恰好为 $[l,r]$，则直接返回其对应的元素和。否则，我们需要将区间 $[l,r]$ 拆分成两个子区间 $[l,mid]$ 和 $[mid+1,r]$，分别递归查询左右子树，最后将其结果合并即可。

下面是基于线段树实现的一个例子：

class SegmentTree {
  constructor(nums) {
    this.nums = nums;
    this.tree = new Array(nums.length * 4).fill(0);
    this.build(0, 0, nums.length - 1);
  }

  build(node, start, end) {
    if (start === end) {
      this.tree[node] = this.nums[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(node * 2 + 1, start, mid);
      this.build(node * 2 + 2, mid + 1, end);
      this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
    }
  }

  update(node, start, end, i, val) {
    if (start === end) {
      this.nums[i] = val;
      this.tree[node] = val;
    } else {
      const mid = Math.floor((start + end) / 2);
      if (i >= start && i <= mid) {
        this.update(node * 2 + 1, start, mid, i, val);
      } else {
        this.update(node * 2 + 2, mid + 1, end, i, val);
      }
      this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
    }
  }

  query(node, start, end, i, j) {
    if (i > end || j < start) {
      return 0;
	} else if (i <= start && j >= end) {
		return this.tree[node];
	} else {
		const mid = Math.floor((start + end) / 2);
		const leftSum = this.query(node * 2 + 1, start, mid, i, j);
		const rightSum = this.query(node * 2 + 2, mid + 1, end, i, j);
		return leftSum + rightSum;
	}
  }
}

// 使用示例
const nums = [1, 3, 5, 7, 9, 11];
const tree = new SegmentTree(nums);

console.log(tree.query(0, 0, nums.length - 1, 2, 4)); // 输出 15
tree.update(0, 0, nums.length - 1, 3, 8);
console.log(tree.query(0, 0, nums.length - 1, 2, 4)); // 输出 18

在上面的代码中，我们定义了一个名为 SegmentTree 的类，它包含了建立线段树、修改元素、查询区间元素和等方法。在构造函数中，我们先初始化了线段树的数组，并通过 build 方法建立线段树。在 update 方法中，我们首先递归找到要修改的节点，然后将其值修改为新的值，同时更新该节点的父节点和祖先节点。在 query 方法中，我们首先判断当前节点的区间与查询区间是否有交集，如果没有则返回 0；如果当前节点的区间包含在查询区间中，则直接返回该节点的元素和；否则我们需要将查询区间拆分成两个子区间，分别递归查询左右子树，最后将其结果合并。

通过上面的代码，我们可以方便地实现对数组的修改和区间求和操作，而且时间复杂度为 $O(\log n)$。