廊坊seo优化公司_微信公众号开发创新_个人免费建站系统_seo作弊

蓝桥杯刷题 Day5 线段树

---

---

前言

今天写牛客网模板题中数据结构的线段树

---

完整代码

一、树状数组

原题地址: 线段树

import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 输入int n = input.nextInt();int q = input.nextInt();int[] a = new int[n+1]; // 用了最低有效位，数组应扩容// 调用线段树类,传入n设定数组范围SegmentTree tree = new SegmentTree(n);// 初始化树状数组，分层管理for (int i = 1; i <= n; i++) {a[i] = input.nextInt();tree.update(i, a[i]);}// 处理查询while(q-- > 0){int op = input.nextInt();if(op == 1){int i = input.nextInt();int k = input.nextInt();tree.update(i, k); // 单点更新}if(op == 2){int l = input.nextInt();int r = input.nextInt();System.out.println(tree.query(r) - tree.query(l - 1)); // 区间求和}}}
}class SegmentTree{private long[] tree; // 存储数组大小public SegmentTree(int n){tree = new long[n + 1]; // 索引0不使用}// 单点更新：将k添加到i位置，向上更新所有层级public void update(int i, int k){while(i < tree.length){tree[i] += k;i += lowBit(i); // 父节点索引}}// 前缀和查询public long query(int index){long sum = 0;while(index > 0){sum += tree[index];index -= lowBit(index); // 向左更新区间}return sum;}// 计算最低有效位（定位父子节点区间）private int lowBit(int x){return x & (-x);}
}

1. 解题思路

1.1 问题抽象

1. 更新ai
2. 计算区间和

1.2 核心思想

1. 分层管理，多个子节点求和成父节点
2. lowBit()最低有效位

1.2 适用条件：

• 数据量极大（例如10⁶级别）
• 需要频繁的单点更新和前缀和/区间和查询

1.3典型应用：

• 实时数据监控（股票、物流）
• 动态排名系统（游戏积分榜）
• 算法竞赛中的优化题（如逆序对统计）

2. 拆解代码

2.1 主函数

2.1.1 输入以及初始化

 Scanner input = new Scanner(System.in);// 输入int n = input.nextInt();int q = input.nextInt();int[] a = new int[n+1]; // 用了最低有效位，数组应扩容// 调用线段树类,传入n设定数组范围SegmentTree tree = new SegmentTree(n);// 初始化树状数组for (int i = 1; i <= n; i++) {a[i] = input.nextInt();tree.update(i, a[i]);}

2.1.2 处理查询

// 处理查询while(q-- > 0){int op = input.nextInt();if(op == 1){int i = input.nextInt();int k = input.nextInt();tree.update(i, k); // 单点更新}if(op == 2){int l = input.nextInt();int r = input.nextInt();System.out.println(tree.query(r) - tree.query(l - 1)); // 区间求和}

2.2 SegmentTree类

2.2.1 初始化数组以及最低有效位

  private long[] tree; // 存储数组大小public SegmentTree(int n){tree = new long[n + 1]; // 索引0不使用}// 计算最低有效位（定位父子节点区间）private int lowBit(int x){return x & (-x);}

2.2.2 单点更新与集区间求和

    // 单点更新：将k添加到i位置public void update(int i, int k){while(i < tree.length){tree[i] += k;i += lowBit(i); // 父节点索引}}// 前缀和查询，1~indexpublic long query(int index){long sum = 0;while(index > 0){sum += tree[index];index -= lowBit(index); // 找前驱区间}return sum;}

二、 题后收获

3.1 知识点

1. 最低有效位：对于二进制来说，保留最右侧的1，其余均为0；